Hewlett Packard Enterprise Development LP

Hewlett-packard Development Company, L.P.

Ron Roth

Erik Ordentlich

Catherine Graves

Giacomo Pedretti

Richard H Henze

John Paul Strachan

Chris Michael Brueggen

Tobias Frederic Ziegler

Pedro Henrique Rocha Bruel

Luca Buonanno

Examples of the presently disclosed technology provide a methodology for detecting and correcting errors in a summing content-addressable memory (Σ-CAM) while the Σ-CAM is performing a computational task (i.e., 'on-access' error correction). The methodology involves adding redundancy columns to a Σ-CAM used to store a task-driven matrix (i.e., a matrix having values comporting with a computational task). Examples can leverage an encoder to compute redundancy values for the redundancy columns such that the Σ-CAM stores a codeword of a linear code (C) in each row. Examples also modify the linear code (C) used to compute redundancy values. Namely, examples modify the linear code (C) so that it includes the all-one vector. With this modification, a system of the presently disclosed technology can detect and correct errors in an output vector from a Σ-CAM based on this modified/particularized linear code (C).

On-access error correction for content-addressable memory

Systems and methods are provided for implementing a low power and area ternary content addressable memory (TCAM). An example of a TCAM comprises a match line, and a plurality of TCAM cells connected along the match line. Each TCAM cell stores a state of a threshold value. The TCAM cells are configured to pull down a signal over the match line in response to inequality between an input search and the threshold value. The plurality of TCAM cells comprises a number of TCAM cells that is less than the threshold value. The input values can be encoded according to a first encoding scheme and the threshold value can be encoded according to one of a second and a third encoding scheme based on an inequality check mapped to the plurality of TCAM cells.

Inequality check with ternary cam

Examples increase precision for aCAMs by converting an input signal (x) received by a circuit into a first analog voltage signal (V(x)) representing the most significant bits of the input signal (x) and a second analog voltage signal (V(x)) representing the least significant bits of the input signal (x). By dividing the input signal (x) bit-wise into the first analog voltage signal (V(x)) and the second analog voltage signal (V(x)), the circuit can utilize aCAM sub-circuits implementing a combination of Boolean operations to search the input signal (x) against 2programmable levels, where 'M' represents the number of programmable bits for each aCAM sub-circuit. Thus, using similar circuit hardware, example circuits square the number of programmable levels of conventional aCAMs (which generally only have 2programmable levels). Accordingly, examples provide new aCAMs that can carry out more complex computations than conventional aCAMs of comparable cost, size, and power consumption.

Increased precision analog content addressable memories

Examples of the presently disclosed technology provide new circuits for detecting errors in aCAMs with improved efficiency. Specifically designed around the structure and operation of aCAM arrays, these circuits include counter sub-circuits electrically connected to match lines of aCAM rows such that the counter sub-circuits receive match-related signals output from aCAM rows. The value stored by a counter sub-circuit may change in response to receiving a match signal, and may remain the same in response to receiving a mismatch signal. As will be described in greater detail below, the stored value of the counter sub-circuit may be used to detect/identify an error in its associated aCAM row after a set of (specially-computed) error-detection input vectors are sequentially applied to the circuit.

Error-detection schemes for analog content-addressable memories

A fault-tolerant analog computing device includes a crossbar array having a number l rows and a number n columns intersecting the l rows to form l&#xd7;n memory locations. The l rows of the crossbar array receive an input signal as a vector of length l. The n columns output an output signal as a vector of length n that is a dot product of the input signal and the matrix values defined in the l&#xd7;n memory locations. Each memory location is programmed with a matrix value. A first set of k columns of the n columns is programmed with continuous analog target matrix values with which the input signal is to be multiplied, where k&#x3c;n. A second set of m columns of the n columns is programmed with continuous analog matrix values for detecting an error in the output signal that exceeds a threshold error value, where m&#x3c;n.

Fault-tolerant analog computing

Examples disclosed herein relate to a fault-tolerant dot product engine. The fault-tolerant dot product engine has a crossbar array having a number l of row lines and a number n of column lines intersecting the row lines to form l&#xd7;n memory locations, with each memory location having a programmable memristive element and defining a matrix value. A number l of digital-to-analog converters are coupled to the row lines of the crossbar array to receive an input signal and a number n of analog-to-digital converters are coupled to the column lines of the crossbar array to generate an output signal. The output signal is a dot product of the input signal and the matrix values in the crossbar array, wherein a number m&#x3c;n of the n column lines in the crossbar array are programmed with matrix values used to detect errors in the output signal.

Fault-tolerant dot product engine

Examples disclosed herein relate to very large-scale integration (VLSI) circuit implementations of list decode circuits. In accordance with some examples disclosed herein, a device may include a first and second polynomial evaluation circuit, a field division circuit, a discrepancy filter, and an enhanced error locator polynomial (ELP) circuit. The first and second polynomial evaluation circuits may respectively evaluate a first and second polynomial output from a Berlekamp-Massey algorithm over a plurality of values in a finite field. The field division circuit may divide the outputs from the evaluations to generate a plurality of speculative discrepancy values for an additional iteration of the Berlekamp-Massey algorithm. The discrepancy filter circuit may filter the speculative discrepancy values down to a list of potentially valid discrepancy values that may be used by the enhanced ELP circuit to generate an enhanced ELP.

List decode circuits

Bit-flip coding uses a bit-flip encoder to flip bits in a redundancy-intersecting vector of a binary array having n rows and n columns until Hamming weights of the binary array are within a predetermined range &#x394; of n divided by two. Information bits of an input data word to the bit-flip coding apparatus are stored in locations within the binary array that are not occupied by n redundancy bits of a redundancy vector.

Bit-flip coding

In one implementation, a data storage system includes a memory array having memory devices in a crossbar configuration, and a memory controller for controlling data storage in the memory array. The memory controller includes an encoder to generate a 2-dimensional encoded bit pattern that encodes an input data. Each run-length of 0's and each run-length of 1's in each row or each column of the encoded bit pattern are at least of a predefined lower limit. The predefined lower limit is at least two. The memory controller includes a write controller to write the encoded bit pattern into the memory devices of the memory array, such that a number of consecutive memory devices in each row or each column of the memory array having a same state is based on the encoded bit pattern.

Storing run-length limited two-dimensional encoded bit patterns in memory arrays

Encoding or decoding can operate a processing system to apply one or more recursive relations to a known parameter associated with a length m and a Hamming weight l to produce a computed parameter associated with length m&#x2212;1. An encoding process can thus assign values to bits of a code based on comparison of the data value being encoded and the computed parameter. A decoding process can use the computed parameters in a calculation of a decoded data value.

Constant hamming weight coding

Methods and systems for storing data in memory arrays are described. In one implementation, input bits are encoded into an intermediate binary array having multiple sub-arrays iteratively appended row-wise to the intermediate binary array. First sub-array is generated based on the input bits such that each row of the first sub-array has a number of 1's equal to a fraction of number of columns in the first sub-array, and based on a column balance coding such that the columns of the first sub-array have an equal number of 1's. At least one subsequent sub-array is generated based on a set of bits obtained from balancing termination indices for a previous sub-array and from diagonal bits of the intermediate binary array that are a part of the previous appended sub-array. The intermediate binary array is transformed to an encoded bit pattern. The encoded bit pattern is stored in the memory array.

Data storing in memory arrays

A method of storing data in a memory array with less than half of memory elements in any row and column in a low-resistance state. The data are arranged in a first portion of an encoding array. High-resistance values are entered in a second portion. A codeword is selected from a covering code for each row in which too many entries have low-resistance values. The selected codeword is used to reduce the number of low-resistance values in that row. A codeword is selected for each column in which too many entries have low-resistance values and the codeword is used to reduce the number of such values in that column. The process is repeated until no row and no column has too many low-resistance values. The array entries are stored in corresponding memory elements.

Growing community of inventors

Palo Alto, CA, United States of America

Ron Roth