Belief propagation processor
AssigneeAnalog Devices, Inc.
InventorsDavid Reynolds, Benjamin Vigoda, Alexander Alexeyev
Life of this patent
Estimating the term…
Abstract
A processor includes a first memory module for storing a first set of storage values each representing a respective input, and a second memory module for storing a second set of storage values in analog form. An analog module is coupled to the first and the second memory modules. The analog module is configured to, in each operation cycle of at least one iteration, update at least some of the second set of storage values based on the first and the second sets of storage values. An output module is for generating a set of outputs from at least some of the second set of storage values.
Claims25
An analog processor for error correction of a parity check code, the parity check code having a plurality of parity constraints on input values of an input frame, the processor comprising:
- an intermediate value memory comprising a plurality of memory elements, each memory element being associated with a different corresponding combination of a constraint and an input value;
- a plurality of analog computation modules each for performing an analog computation associated with a parity constraint of the code, each input of the computation modules being connectable to a selected plurality of the memory elements and each output of the computation modules being connectable to a selected memory element;
- and
- a controller for sequencing operation of the processor in a series of iterations, and in each iteration in a series of cycles, wherein in each cycle the controller configures connections of inputs and outputs of each analog computation module to perform a computation associated with one of the parity constraints of the parity check code, including connecting each output of each analog computation module to a memory element associated with the parity constraint and connecting each input of the analog computation module to a memory element associated with an input value used in the parity constraint, wherein in each cycle, no memory element is connected to both an input and an output of any of the analog computation modules.
A method for operating an analog processor for error correction of a parity check code, the parity check code having a plurality of parity constraints on input values of an input frame, the method comprising:
- maintaining values in an intermediate value memory comprising a plurality of memory elements, each memory element being associated with a different corresponding combination of a constraint and an input value;
- and
- sequencing operation of the processor in a series of iterations, and in each iteration in a series of cycles, wherein in each cycle connections of inputs and outputs of each module of a plurality of analog computation modules are configured to perform a computation associated with one of the parity constraints of the parity check code, including connecting each output of the analog computation module to a memory element associated with the parity constraint and connecting each input of each analog computation module to a memory element associated with an input value used in the parity constraint, wherein in each cycle, no memory element is connected to both an input and an output of any of the analog computation modules.
An analog processor comprising:
- a first memory module for storing a first set of storage values in respective storage elements each representing a respective input to the processor;
- a second memory module for storing a second set of storage values in analog form in respective storage elements, the second set of storage values including intermediate values determined during operation of the processor, the second memory module including a plurality of memory sections, groups of the sections forming banks;
- a plurality of analog computation modules coupled to the first and the second memory modules, the processor being configurable such that in each of a plurality of operation cycles the analog computation modules determine values for at least some of the second set of storage values based on at least some of the first and the second sets of storage values, said analog computation modules being concurrently operable to determines values for different subsets of the second set of storage values in each operation cycle, wherein for each of the analog computation modules each input of a plurality of inputs to the analog computation module is associated with a different bank of the memory sections;
- and
- an output module for generating a set of outputs from at least some of the second set of storage values;
- wherein the analog processor is configurable such that in each cycle, each memory section includes memory elements that either provide values to one or more of the analog computation modules or memory elements that are updated with values from the one or more analog computation modules.
Dependencies are inferred from the claim text.