Belief propagation processor

• US 8,799,346 B2
• Filed: 04/04/2011
• Issued: 08/05/2014
• Est. Priority Date: 03/02/2009
• Status: Active Grant

• Current Assignee: Analog Devices, Inc., Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Reynolds, David, Vigoda, Benjamin
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US13/079,204
• Publication Number:
  US 20110295786A1
• Time in Patent Office: 1,219 Days
• Field of Search: 708/801
• US Class Current: 708/801
• CPC Class Codes: G06G 7/122 for optimisation, e.g. least square fitting, linear programming, critical path analysis, gradient method
• CPC Class Codes: G06G 7/1942 for forming other integrals of product, e.g. orthogonal functions, Laplace, Laguerre, Walsh, Hadamard, Hilbert G06G7/195, G06G7/1907 and G06G7/1914 take precedence
• CPC Class Codes: H03M 13/1111 Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms
• CPC Class Codes: H03M 13/1137 Partly parallel processing, i.e. sub-blocks or sub-groups of nodes being processed in parallel
• CPC Class Codes: H03M 13/1188 wherein in the part with the double-diagonal at least one column has an odd column weight equal or greater than three
• CPC Class Codes: H03M 13/6597 Implementations using analogue techniques for coding or decoding, e.g. analogue Viterbi decoder

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.

Claims

1. 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, the second set of storage values including intermediate values determined during operation of the processor;

an analog computation module coupled to the first and the second memory modules, the analog processor being configurable such that in each of a plurality of operation cycles the analog computational module determines 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; and

an output module for generating a set of outputs at least in part from the at least some of the second set of storage values.

2. The analog processor of claim 1 wherein the first storage module is configured to store the first set of storage values in analog form.

3. The analog processor of claim 1 wherein the analog computation module is linked to the first and the second memory modules via analog signal paths.

4. The analog processor of claim 3 in which the analog signal paths are each configured to carry a value on a conductor represented as at least one of a voltage and a current proportional to the value.

5. The analog processor of claim 1, wherein the analog computational module is configurable to determine values for a different subset of the second set of storage values in corresponding cycles of the plurality of operation cycles.

6. The analog processor of claim 1 further comprising input selection circuitry configurable to couple the analog computation module to outputs of selected memory elements of the first and the second memory modules.

7. The analog processor of claim 1 further comprising, for each analog computation module, a plurality of signal busses, each bus providing an input value to the analog computation module and being switchably coupled to a plurality of the storage elements of the second memory module.

8. The analog processor of claim 7 wherein the storage elements are coupled to switchably provide a current representation of a storage value stored in the storage element such that the input value provided to the analog computation module is represented as a current that is substantially proportional to a sum of the currents representations provided by the storage elements.

9. The analog processor of claim 1 further comprising output section circuitry configurable to accept outputs of selected memory elements of the first and the second memory modules, and to determine outputs of the analog processor.

10. The analog processor of claim 1 comprising a plurality of analog computation modules, said modules being concurrently operable to determines values for different subsets of the second set of storage values in each operation cycle.

11. The analog processor of claim 10 wherein the second memory module includes a plurality of sections, each associated with a corresponding different one of the analog computation modules for storing values determined by the analog computation module.

12. The analog processor of claim 10 wherein the second memory module is configured such that in a single operation cycle, each storage element can provide a storage value to one or more of the analog computation modules and can accept a determined value to store in the storage element for providing in a subsequent operation cycle.

13. The analog processor of claim 12 wherein each storage element is associated with two storage locations such that in any one cycle, one storage location being used for accepting a determined value and another storage location being used for providing a value.

14. The analog processor of claim 10 wherein the second memory module includes a plurality of memory sections, groups of the sections forming banks, wherein for each of the analog computation modules each of a plurality of inputs to the module is associated with a different bank of the memory sections.

15. The analog processor of claim 1 configured to implement a belief propagation computation.

16. The analog processor of claim 1 configured to implement a factor graph computation.

17. The analog processor of claim 16 wherein the a analog processor is configured to implement a decoder for a low density parity check (LDPC) code.

18. The analog processor of claim 1 further comprising:

a controller configured to control operation of the analog processor to perform a plurality of iterations of computation, each iteration comprising the plurality of computation cycles.

19. The analog processor of claim 18 wherein the plurality of computation cycles is substantially the same in each iteration, each cycle being associated with a configuration of the first and the second storage modules to provide inputs and output to one or more analog computation modules.

20. The analog processor of claim 18 wherein the analog processor is at least one of configured and configurable to implement a decoder parity check code, and each cycle is associated with one or more parity check constraints, and wherein the cycles of each iteration are together associated with all the parity check constraints of the code.

21. The analog processor of claim 1 wherein the analog computation module implements a network of analog processing elements.

22. The analog processor of claim 21 wherein the analog processing elements include elements that represent soft logical operations.

23. The analog processor of claim 22 wherein the soft logical operations include soft XOR operations.

24. The analog processor of claim 21 wherein the network of elements is acyclic.

25. The analog processor of claim 21 wherein the network of elements includes at least one cycle of elements, the analog computation module being configured to implement a relaxation computation.