The Royal Institution for the Advancement of Learning / Mcgill University

Huawei Technologies Co., Limited

University of California

Mcgill University

Warren Jeffrey Gross

Gabi Sarkis

Shie Mannor

Pascal Giard

Thibaud Tonnellier

Yiqun Ge

Saeed Sharifi Tehrani

Francois Leduc-Primeau

Saied Hemati

Adam Christian Cavatassi

Huayi Zhou

Camille Leroux

Claude Thibeault

Alexander Vardy

Naoya Onizawa

Ido Tal

Ali Naderi

Amir Ardakani

Arash Ardakani

Marwan Jalaleddine

Ryan Meng Yong Seah

Dennis Giannacopoulos

Yousef El Kurdi

Syed Mohsin Abbas

Alexandre Raymond

There is provided a computer-implemented method of training a neural network, the neural network comprising a plurality of interconnected nodes arranged in a plurality of layers and having a plurality of weights associated therewith. The method comprises obtaining, at a computing device, a training dataset from a database, performing, at the computing device, a forward propagation on the training dataset to produce an output of the neural network, and performing, at the computing device, a backward propagation on the output of the neural network to update the plurality of weights, the backward propagation performed using an estimation of a polarity and a neutrality of gradients of the neural network.

Method and system for training a neural network

An optimization-based decoder with improved performance and cyclic redundancy check is provided. An optimization problem is generated and solved. The optimization problem includes a function implementing constraints on variables. Main variables correspond to nodes of the encoding graph, including input variables corresponding to output nodes and output variables corresponding to input nodes. Ancillary variables correspond to an additional output a logical operations in the encoding graph. Constraints are configured to generate cost penalties, for instance when the main and ancillary variables of a candidate solution disagree with conditions of the encoding graph, and to correspond with the cross-entropy between each codeword symbol and the corresponding input variable. A candidate solution is obtained by solving the optimization problem, wherein the output variables in the candidate solution correspond to decoded symbols.

Polar decoder and associated method

A method for decoding data comprises receiving a sequence of symbols from a data sender over a noisy data channel. At a first decoder, a first search for a candidate error pattern is performed, within a search region, among a plurality of candidate error patterns, and an indication of a failure of the first search is output to a second decoder when no candidate error pattern is found within the search region. At the second decoder, a second search is performed, in parallel with the first search, for the candidate error pattern by evaluating the candidate error patterns for codebook membership based on the sequence of symbols, one or more of the candidate error patterns being skipped from the second search based on the indication of the failure of the first search. The sequence of symbols is decoded based on an outcome of the first search and the second search.

System and method for decoding data

Systems and methods of communicating using asymmetric polar codes are provided which overcome the codeword length constraints of systems and methods of communicating that use traditional polar codes. Used herein, asymmetric polar codes refers to a polarizing linear block code of any arbitrary length that is constructed by connecting together constituent polar codes of unequal length. Asymmetric polar codes may be known by other names. In comparison to conventional solutions for variable codeword length, asymmetric polar codes may provide more flexibility, improved performance, and/or reduced complexity of decoding, encoding, or code design. The system and method provide a flexible, universal, and well-defined coding scheme and to provide sound bit-error correction performance and low decoding latency (compared with current length-compatible methods which can be used with current hardware designs). For the most part, the provided embodiments can be implemented with nearly all available current encoding/decoding polar code techniques.

Method and apparatus for wirelessly communicating over a noisy channel with a variable codeword length polar code to improve transmission capacity

There is provided a method comprising, at a data receiver, receiving a channel codeword from a data sender over a noisy data channel, generating a plurality of candidate error patterns, the plurality of candidate error patterns comprising a plurality of one-bit error patterns and a plurality of multiple-bit error patterns generated from the plurality of one-bit error patterns, evaluating the plurality of candidate error patterns for codebook membership, based on the channel codeword, and outputting an estimated codeword when a codebook membership constraint is satisfied for a given candidate error pattern.

Architecture for guessing random additive noise decoding (GRAND)

Methods and systems for encoding data are described herein. The method comprises inputting data to a first pipeline of a non-systematic polar encoder capable of encoding a polar code of length n, extracting, via at least one first multiplexer of size log n&#xd7;1, a first polar code of length n&#x3c;nat a first location along the first pipeline to generate a first encoded output, modifying the first encoded output to set frozen bits to a known value to obtain a modified first encoded output, inputting the modified first encoded output to a second pipeline of the non-systematic polar encoder, and extracting, via at least one second multiplexer of size log n&#xd7;1, a second polar code of length n&#x3c;nat a second location along the second pipeline to generate a second encoded output, the second encoded output corresponding to a systematically encoded polar code of length n.

Flexible polar encoders and decoders

Internet routers are a key component in today's Internet. Each router forwards received packets toward their final destinations based upon a Longest Prefix Matching (LPM) algorithm select an entry from a routing table that determines the closest location to the final packet destination among several candidates. Prior art solutions to LPM lookup offer different tradeoffs and that it would be beneficial for a design methodology that provides for low power large scale IP lookup engines addressing the limitations within the prior art. According to embodiments of the invention a low-power large-scale IP lookup engine may be implemented exploiting clustered neural networks (CNNs). In addition to reduced power consumption embodiments of the invention provide reduced transistor count providing for reduced semiconductor die footprints and hence reduced die cost.

Methods and systems for network address lookup engines

Herein provided are methods and systems for generating finite element modelling results. Finite element method (FEM) data relating to establish a FEM problem to be solved for a portion of a physical system being analyzed is received. A FEM mesh comprising at least FEM mesh node locations relating to the portion of the physical system is generated. FEM mesh values for each FEM mesh node location are automatically generated with a microprocessor. A factor graph model comprising a plurality of random variable nodes and a plurality of factor nodes is automatically generated with a microprocessor based upon the FEM mesh node locations. A set of belief propagation update rules are automatically executed upon the factor graph model using Gaussian function parametrization and the FEM mesh values. The belief propagation update rules are iteratively executed until a predetermined condition has been met.

Finite element methods and systems

There is described a multi-mode unrolled decoder. The decoder comprises a master code input configured to receive a polar encoded master code of length N carrying k information bits and N&#x2212;k frozen bits, decoding resources comprising processing elements and memory elements connected in an unrolled architecture and defining an operation path between the master code input and an output, for decoding a polar encoded code word, at least one constituent code input configured to receive a polar encoded constituent code of length N/p carrying j information bits and N/p&#x2212;j frozen bits, where p is a power of 2, and at least one input multiplexer provided in the operation path to selectively transmit N/p bits of one of the master code and the constituent code to a subset of the decoding resources.

Multi-mode unrolled polar decoders

Modern communication systems must cope with varying channel conditions and differing throughput constraints. Polar codes despite being the first error-correcting codes with an explicit construction to achieve the symmetric capacity of memoryless channels are not currently employed against other older coding protocols such as low-density parity check (LDPC) codes as their performance at short/moderate lengths has been inferior and their decoding algorithm is serial leading to low decoding throughput. Accordingly techniques to address these issues are identified and disclosed including decoders that decode constituent codes without recursion and/or recognize classes of constituent directly decodable codes thereby increasing the decoder throughput. Flexible encoders and decoders supporting polar codes of any length up to a design maximum allow adaptive polar code systems responsive to communication link characteristics, performance, etc. while maximizing throughput. Further, designers are provided flexibility in implementing either hardware or software implementations.

Herein provided are methods and systems for decoding polar codes. A data flow graph relating to a predetermined polar code is converted to a tree graph comprising rate-zero nodes, rate-nodes, and rate-R nodes. A rate-R node within the binary tree is replaced with a maximum likelihood node when predetermined conditions are met thereby replacing a sub-tree of the tree graph with a single maximum likelihood node.

Methods and systems for decoding polar codes

A polar code decoder includes: processing elements each receiving a pair of input values and applying a first or a second predetermined mathematical function depending on a provided function control signal; a first memory that stores at least one of the outputs from processing elements and a plurality of channel values relating to a received polar code to be decoded; a second memory that stores indices of a plurality of frozen bits each representing a bit within an information-bit vector of the polar code being decoded; and a computation block that receives a plurality of inputs from a portion of the processing elements and generates an output that is can be set to a predetermined frozen value or to a calculated value, depending on whether a current index of the bit being decoded is indicated as frozen or not frozen.

A method for iteratively decoding a set of encoded samples received from a transmission channel is provided. A data signal indicative of a noise level of the transmission channel is received. A scaling factor is then determined in dependence upon the data signal and the encoded samples are scaled using the scaling factor. The scaled encoded samples are then iteratively decoded. Furthermore, a method for initializing edge memories is provided. During an initialization phase initialization symbols are received from a node of a logic circuitry and stored in a respective edge memory. The initialization phase is terminated when the received symbols occupy a predetermined portion of the edge memory. An iterative process is executed using the logic circuitry storing output symbols received from the node in the edge memory and a symbol is retrieved from the edge memory and provided as output symbol of the node. Yet further an architecture for a high degree variable node is provided. A plurality of sub nodes forms a variable node for performing an equality function in an iterative decoding process. Internal memory is interposed between the sub nodes such that the internal memory is connected to an output port of a respective sub node and to an input port of a following sub node, the internal memory for providing a chosen symbol if a respective sub node is in a hold state, and wherein at least two sub nodes share a same internal memory.

Methods and systems for improving iterative signal processing

Low-Density Parity-Check (LDPC) codes offer error correction at rates approaching the link channel capacity and reliable and efficient information transfer over bandwidth or return-channel constrained links with data-corrupting noise present. LDPC codes also offer error correction performance approaching channel capacity exponentially fast in terms of the code length, linear processing complexity, and parallelism that scales with the code length. They also offer challenges relating to the decoding complexity of the binary error-correction codes themselves and error floors limiting achievable bit-error rates. A new Relaxed Half-Stochastic (RHS) decoding algorithm is presented that reduces decoding complexity for high decoding throughput applications. The RHS algorithm uses an approach based on stochastic decoding algorithms but differs significantly from the conventional approaches of LDPC decoder implementation. The RHS algorithm also leads to a randomized decoding technique called redecoding that addresses the error floor limitation.

Growing community of inventors

Cote-St-Luc, Canada

Warren Jeffrey Gross