SYSTEMS, DEVICES, AND METHODS FOR ESTIMATION

• US 20120066172A1
• Filed: 11/17/2011
• Published: 03/15/2012
• Est. Priority Date: 05/20/2009
• Status: Active Grant

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Jebara, Tony
• Granted Patent: US 8,825,566 B2
• Time in Patent Office: Days
• US Class Current: 706/52
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

A system, method and computer-readable medium for maximum a posteriori (MAP) estimation of a graphical model are disclosed. The MAP estimation process can include obtaining an encoded data message sent over a 4G cellular wireless network and generating a graphical model representation of the message. The graphical model can be converted into a nand Markov random field (NMRF). The MAP estimation process can also include determining whether the NMRF has a perfect graph structure, and solving for a MAP estimate configuration of the NMRF. The MAP estimation process can further include outputting the MAP estimate configuration, an indication of the MAP estimate configuration, and/or a result based on a combination of the MAP estimate configuration and the encoded data message (e.g., a decoded message).

Claims

1. A system for decoding an encoded data message, the system comprising:

a processor;

an interface coupled to the processor and configured to receive the encoded data message; and

a data store coupled to the processor and storing a nand Markov random field (NMRF) network representing the value of output configurations conditioned on the encoded data message,

the data store further storing a procedure for deriving at least one a posteriori estimation from the encoded data message, and

the data store further storing a procedure for outputting a decoded data message based on the at least one a posteriori estimation.

2. The system of claim 1, wherein the encoded data message is a noisy signal delivered over a cellular wireless network communications channel and the at least one a posteriori estimation includes a maximum a posteriori (MAP) estimation indicating disambiguated information content of the noisy signal.

3. The system of claim 2, wherein the cellular wireless network is a 4G network.

4. The system of claim 1, wherein the encoded data message is lossy data delivered over a cellular wireless network communications channel and the at least one a posteriori estimation includes a maximum a posteriori estimation indicating recovered information content of the lossy data.

5. The system of claim 4, wherein the processor is a portion of a 4G chipset.

6. The system of claim 1, wherein the encoded data message is encoded with a concatenated code and the procedures for deriving and for outputting are both adapted to produce a decoded concatenated code data message.

7. The system of claim 1, wherein the deriving at least one a posteriori estimation includes a message passing function and the NMRF includes a perfect graph.

8. The system of claim 7, wherein the message passing function includes passing independent scalars from a first node to each of one or more neighbor nodes of the first node, the two scalars being nontrivial and each being determined using respective non-identical maximum functions.

9. A nontransitory computer-readable storage medium having stored thereon software instructions that, when executed by a processor in a 4G chipset, cause the processor to perform operations comprising:

obtaining a graphical model of an encoded data message received from a cellular wireless network;

converting the graphical model into a nand Markov random field (NMRF);

computing a MAP estimate configuration of the NMRF using belief propagation; and

outputting a decoded data message based on the MAP estimate configuration.

10. The nontransitory computer-readable storage medium of claim 9, wherein the cellular wireless network is a 4G network.

11. The nontransitory computer-readable storage medium of claim 9, further comprising determining whether the NMRF has a perfect graph structure by determining if the NMRF is a Berge graph, the converting being performed responsively to an indication that the NMRF has a perfect graph structure determined by said determining.

12. The nontransitory computer-readable storage medium of claim 9, wherein the belief propagation includes performing a message passing function according to stored software instructions, the message passing function including passing independent scalars from a first node to each of one or more neighbor nodes of the first node, the two scalars being nontrivial and each being determined using respective non-identical maximum functions.

13. A computerized method for processing a received 4G cellular wireless communication signal, the method comprising:

receiving, at a radio frequency receiver, an input signal including an encoded data message, the input signal being subject to having data errors introduced during transmission;

obtaining a nand Markov random field (NMRF) using a signal processor programmed to decode data messages with a maximum a posteriori (MAP) configuration estimating function, the NMRF model having a perfect graph structure, the signal processor configured to operate as a portion of a 4G chipset;

combining the encoded data message with the NMRF using the signal processor to obtain a modified NMRF;

processing the modified NMRF, using the signal processor, to obtain a MAP estimate configuration of the NMRF; and

generating decoded data from the encoded data message using the MAP estimate configuration of the NMRF.

14. The method of claim 13, wherein obtaining the NMRF includes retrieving a previously generated NMRF from a data storage device.

15. The method of claim 14, further comprising adjusting weight values for the NMRF based on the received encoded data message.

16. The method of claim 15, further comprising altering connectivity of the NMRF based on the received encoded data message.

17. The method of claim 13, wherein obtaining the NMRF includes generating an NMRF based on an encoding scheme used to encode the received encoded data message.

18. The method of claim 13, wherein computing the modified NMRF includes using the signal processor programmed to perform convergent message passing.

19. The method of claim 18, wherein the convergent message passing includes passing messages in a unipartite belief propagation network.

20. The method of claim 18, wherein the convergent message passing includes passing messages in a bipartite belief propagation network.