Browse Prior Art Database

System and Method for Minimum Hamming Distance Discovery Using Neuromorphic Hardware

IP.com Disclosure Number: IPCOM000248510D
Publication Date: 2016-Dec-12
Document File: 7 page(s) / 130K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a neuromorphic/spiking implementation of an algorithm for efficiently calculating the minimum Hamming distances between sequences of input binary strings and an ordered set of stored binary strings, effectively returning an index into the stored ordered set that is closest to the current input string with respect to the Hamming distance metric.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 23% of the total text.

1

System and Method for Minimum Hamming Distance Discovery Using Neuromorphic Hardware

Associative memory or content-addressable memory is a memory that can recall potentially corrupted input patterns by associating the input pattern with the most similar stored memory concept [1]. The Hamming network is an associative memory that finds the Hamming distance between an input pattern and each memory pattern that is stored in memory and returns the stored memory with the smallest hamming distance from the input pattern. Such associative memories have found applications in image processing, pattern recognition, optimization, face detection, network security (e.g., virus detection), and natural language grammar learning [1].

Presented herein is an implementation of a minimum Hamming distance algorithm that can run on a low power neuromorphic architecture, specifically the chip comprising a network of neurosynaptic cores with limited fan-in and fan-out [2,3]. This returns an index into the stored ordered set of binary strings that is closest to the current binary input string with respect to the Hamming distance metric. Any device requiring a low-power envelope can make use of this algorithm, as the hamming distance algorithm described herein can run on parasitic power. In contrast, running the full algorithm on a conventional von Neumann architecture would require significantly more power. Given is an example instance of how the routine could be implemented on neuromorphic hardware [2].

The core idea introduces a corelet for the neuromorphic CPU hardware [3] that encodes user-provided constant binary strings and takes as input through its connectors one (or more) distinct binary string(s) per frame (called "estimated strings"). For each input estimated binary string, the corelet returns the index of the constant binary string with which the estimated binary string has the smallest Hamming distance. A tie breaking mechanism is also used to break ties.

Corelet Parameter Description (argmin hamming distance corelet): · groundTruthVecs: a binary matrix, where the binary string of each row corresponds to one of the constant binary

strings described above. · numIndepVectors: the number of distinct binary strings that will enter via the connector, per frame. It is assumed

that each string's length will equal the length of each row in groundTruthVecs. For each of these distinct/independent strings the algorithm finds the row in groundTruthVecs with the minimum Hamming distance.

· rankTiesIndep: A cell array where the jth element is an array of length equal to the height of matrix groundTruthVectors. The ith element of each array has the rank for the corresponding row/class of groundTruthVecs (starting from 1 for the highest/most important rank)

2

Connectors

The system has one input connector for each column j of groundTruthVecs, with numIndepVectors pins per connector. When the ith pin of connector j accepts a spike as input, it means that the jth element...