Polar decoder and associated method

A system for decoding a noisy codeword, the system comprising:

• a receiver configured for receiving the noisy codeword, wherein the noisy codeword comprises a plurality of codeword symbols corresponding to a plurality of input symbols encoded via an encoder and transmitted via a noisy channel;
• memory for storing variable values;
• and
• a decoder comprising:
• an objective function creation module configured to:
• generate an optimization problem comprising an objective function, the objective function being evaluated according to variables of candidate solutions, said variables comprising:
• a plurality of main variables, each corresponding to one of a plurality of nodes in an encoding graph implemented by the encoder, said main variables comprising input variables at output nodes of the encoding graph and output variables at input nodes of the encoding graph, and
• a plurality of ancillary variables, each corresponding to an additional output of one of a plurality of logical operations in the encoding graph,
• wherein the objective function comprises an aggregation of constraints, the constraints comprising:
• node constraints configured to generate a first cost penalty when the main and ancillary variables of a candidate solution disagree with conditions of the encoding graph implemented by the encoder, and
• receiver constraints configured to generate a second cost penalty corresponding to a cross-entropy between each codeword symbol and a corresponding one of the input variables;
• and
• a solver configured for solving the optimization problem to obtain a candidate solution, wherein the output variables in the candidate solution correspond to decoded symbols.

A non-transitory computer-readable medium storing thereon computer executable instructions for decoding a noisy codeword, the noisy codeword comprising a plurality of codeword symbols corresponding to a plurality of input symbols encoded via an encoder and transmitted via a noisy channel, the instructions, when executed by one or more processors of a computing system, causing the computing system to:

• generate an optimization problem comprising an objective function, the objective function being evaluated according to variables of candidate solutions, said variables comprising:
• a plurality of main variables, each corresponding to one of a plurality of nodes in an encoding graph implemented by the encoder, said main variables comprising input variables at output nodes of the encoding graph and output variables at input nodes of the encoding graph, and
• a plurality of ancillary variables, each corresponding to an additional output of one of a plurality of logical operations in the encoding graph,
• wherein the objective function comprises an aggregation of constraints, the constraints comprising:
• node constraints configured to generate a first cost penalty when the main and ancillary variables of a candidate solution disagree with conditions of the encoding graph implemented by the encoder, and
• receiver constraints configured to generate a second cost penalty corresponding to a cross-entropy between each codeword symbol and a corresponding one of the input variables;
• and
• solve the optimization problem to obtain a candidate solution, wherein the output variables in the candidate solution correspond to decoded symbols.