FIELD OF THE INVENTION

The present invention generally relates to communication systems and more specifically to communication systems that enable transmission by multiple transmitters on a random access channel.

BACKGROUND

Random access (RA) protocols are at the heart of many modern cellular standards for contention resolution over their control channels or for medium access control in wired or wireless local area networks. Almost all these protocols are developed based on variations of the slotted Aloha (SA) or carrier sense multiple access protocols, which can suffer from performance limitations. With the advent of the Internet of things and machine-to-machine communications and the scale of such networks, the overhead associated with current random access protocols when a large number of devices are attempting to transmit short messages may present a significant, performance bottleneck.

Efforts on improving the performance of SA methods include Contention Resolution Diversity Slotted Aloha (CRDSA), which replaces the concept of destructive collisions in SA by successive interference cancellation (SIC) strategies. Specifically, each user is prescribed to send its packet twice over two time-slots of a single contention frame. The receiver then detects the signals received without a collision, and subsequently removes the associated interference from time-slots in which its replica was transmitted. The process iteratively continues until all transmitted packets are recovered. The SIC can be represented by an irregular bipartite graph and users can adopt repetition rates from a given distribution for transmission of each packet. Utilizing density evolution analysis, this distribution can be optimized to maximize throughput. All the work in this domain typically assumes an error free transmission and the loss is only due to collisions that are not resolved. Since errors in the recovery of one packet will propagate and harm the SIC process, the error free assumption is typically addressed using long and low-rate channel codes.

In a number of systems, message passing algorithms between a receiver and the transmitters sharing the channel are utilized to enable multiuser detection. This is indeed the case in sparse coded multiple access systems, where each user is provided with a sparse codebook and the codewords of different users are transmitted over shared orthogonal resources, e.g., OFDM tones. Another related approach is based on analog fountain codes purposely designed for wireless fading channels.

SUMMARY OF THE INVENTION

Systems and methods in accordance with various embodiments of the invention are utilized to communicate over random access channels with erasures in which the number of users in each frame may be unknown at the transmitters, but known at the receiver. In several embodiments, the communication systems employ a two-layer coding architecture for joint contention resolution and erasure correction. In several embodiments, the receiver design employs message passing between the two layers to achieve the joint resolution of collisions and erasures. In many embodiments, the receiver estimates the number of active transmitters and coordinates selection of appropriate codes and/or code rates within the communication system to increase throughput on the shared channel. In many embodiments, the adjustment of the two-layer code utilized within the communication system increases the average user data rate achievable by each active transmitter for the given channel conditions. In several embodiments, the selected two-layer code is the optimal choice from a set of available two-layer coding schemes for the number of active transmitters and/or the observed channel conditions.

One embodiment of the communication system includes:

a plurality of transmitters configured to transmit signals via a random access channel, where each transmitter comprises:an encoder configured to encode a packet of data bits using a two-layer code comprising an inner medium access control code and and an outer error correcting code, where encoding a packet of data bits using the two-layer code comprises:encoding a packet of user data bits using an error correcting code to obtain encoded bits;selecting a repetition rate for each encoded bit; andselecting a subset of bit intervals on which to transmit each encoded bit at its selected repetition rate; anda modulator configured to modulate each encoded bit at its selected repetition rate for transmission via the random access channel during the selected subset of bit intervals;

a receiver configured to receive transmitted signals from the plurality of transmitters via the random access channel, wherein the receiver comprises:a demodulator configured to demodulate received signals and provide input signals to the decoder; andwherein the decoder is configured to:iteratively decode packets of user data bits received from the plurality of transmitters using message passing between an inner medium access control layer and an outer coding layer to jointly perform contention resolution and decoding of user data bits from the input signals received from the demodulator; andoutput decoded packets of user data.

As can readily be appreciated, communication systems in accordance with many embodiments of the invention employ symbol constellations in which multiple bits map to each symbol (i.e. the cardinality of the constellation is greater than two). In embodiments in which multiple bits map to each transmitted symbol, the repetition rate can be determined for each encoded symbol and the modulator selects a subset of symbol intervals on which to transmit each encoded symbol at is selected repetition rate. By extension, bit intervals can be considered to be symbol intervals of systems that employ a binary symbol constellation. Accordingly, communication systems in accordance with various embodiments of the invention are in no way limited to any specific modulation scheme and/or constellation cardinality.

In a further embodiment of the invention, each encoder is configured to select a repetition rate for each encoded bit based upon channel conditions.

In another embodiment of the invention, the selected repetition rate for at least one of the encoded bits is greater than one.

In a still further embodiment, the error correcting code is a Low Density Parity Check Code.

In still another embodiment, the decoder includes a set of check nodes, a set of time nodes, and a set of variable nodes and the decoder performs a decoding iteration starting with the medium access control layer by: the set, of time nodes sending messages containing their estimates of the values of the variable nodes to the set of variable nodes; and updating values at the set of variable nodes based upon the received messages from the set of time nodes. The decoder continues the decoding iteration by performing a round at the code layer including: the set of variable nodes sending their updated values to the set of check nodes; the set of check nodes sending messages containing their estimates of the values of the variable nodes to the set of variable nodes; and further updating values at the set of variable nodes based upon the received messages from the set of check nodes. The decoder completes the decoding iteration at the medium access control layer by the set of variable nodes sending their further updated values to the set of time nodes.

In a yet further embodiment, the decoder continues to iterate until a stopping criterion is reached.

In yet another embodiment, the error correcting code is a short block-length code.

In a further embodiment again, the decoder includes a set of decoders, a set of time nodes, and a set of variable nodes and the decoder performs a decoding iteration starting with the medium access control layer by: the set of time nodes sending messages containing their estimates of the values of the variable nodes to the set of variable nodes; and updating values at, the set of variable nodes based upon the received messages from the set of time nodes. The decoder continues the decoding iteration by performing a round at the code layer including: the set of variable nodes sending their updated values to the set of decoders; the set of decoders sending messages containing their estimates of the values of the variable nodes to the set of variable nodes; and further updating values at the set of variable nodes based upon the received messages from the the set of decoders. The decoder completes the decoding iteration at the medium access control layer by the set of variable nodes sending their further updated values to the set of time nodes.

In another embodiment again, the decoder continues to iterate until a stopping criterion is reached.

In a further additional embodiment, prior to commencement of a frame, the receiver is configured to: determine a number of the plurality of transmitters expected to actively transmit during the frame; and specify code parameters for the two-layer code utilized by the plurality of transmitters when transmitting during the frame based upon the number of the plurality of transmitters expected to actively transmit during the frame. In addition, the plurality of transmitters that actively transmit during the frame are configured to encode packets of user data using the code parameters for the two-layer code specified by the receiver.

In another additional embodiment, the code parameters for the two-layer code comprise at least one code parameter selected from the group consisting of: a code book; a pattern of bit or symbols intervals used to select a subset of bit intervals or a subset of symbol intervals on which to transmit each encoded bit or each encoded symbol at its selected repetition rate; and a repetition rate for an encoded bit or an encoded symbol.

In a still yet further embodiment, the receiver further comprises a transmitter configured to transmit control messages that specify code parameters for the two-layer code utilized by the plurality of transmitters, and each transmitter further comprises a receiver configured to receive control messages transmitted by the receiver.

In still yet another embodiment, the control messages further comprise a beacon message indicating a start of the frame.

An embodiment of a transmitter system includes:

a receiver configured to receive a control message indicating a set of code parameters for a two-layer code;

an encoder configured to encode a packet of data bits using a two-layer code comprising an inner medium access control code and and an outer error correcting code, where encoding a packet of data bits using the two-layer code comprises:encoding a packet of user data bits using an error correcting code to obtain encoded bits in accordance with the set of code parameters;selecting a repetition rate for each encoded bit in accordance with the set of code parameters; andselecting a subset of bit intervals on which to transmit each encoded bit at its selected repetition rate; and

a modulator configured to modulate each encoded bit at its selected repetition rate for transmission via the random access channel during the selected subset of bit intervals.

In a further embodiment, the receiver is further configured to receive a beacon message indicating a start of a frame.

An embodiment of a receiver system configured to receive transmitted signals from a plurality of transmitters via a random access channel includes:

a demodulator configured to demodulate received signals and provide input signals to a decoder; and

wherein the decoder is configured to:iteratively decode packets of user data bits received from a plurality of transmitters using message passing between an inner medium access control layer and an outer coding layer to jointly perform contention resolution and decoding of user data bits from the input signals received from the demodulator; andoutput decoded packets of user data.

In a further embodiment, the outer coding layer utilizes an iterative error correcting code, the decoder comprises a set of check nodes, a set of time nodes, and a set of variable nodes, and the decoder performs a decoding iteration starting with the medium access control layer by: the set of time nodes sending messages containing their estimates of the values of the variable nodes to the set of variable nodes; and updating values at the set of variable nodes based upon the received messages from the set of time nodes. The decoder continues the decoding iteration by performing a round at the code layer including: the set of variable nodes sending their updated values to the set of check nodes; the set of check nodes sending messages containing their estimates of the values of the variable nodes to the set of variable nodes; and further updating values at the set of variable nodes based upon the received messages from the set of check nodes. The decoder completes the decoding iteration at the medium access control layer by the set of variable nodes sending their further updated values to the set of time nodes.

In another embodiment, the outer coding layer uses a short block-length code error correcting code, the decoder comprises a set of decoders, a set of time nodes, and a set of variable nodes, and the decoder performs a decoding iteration starting with the medium access control layer by: the set of time nodes sending messages containing their estimates of the values of the variable nodes to the set of variable nodes; and updating values at the set of variable nodes based upon the received messages from the set of time nodes. The decoder continues the decoding iteration by performing a round at the code layer including: the set of variable nodes sending their updated values to the set of decoders; the set of decoders sending messages containing their estimates of the values of the variable nodes to the set of variable nodes; and further updating values at the set of variable nodes based upon the received messages from the the set of decoders. The decoder completes the decoding iteration at the medium access control layer by the set of variable nodes sending their further updated values to the set of time nodes.

In a still further embodiment, the receiver is configured to: determine a number of transmitters expected to actively transmit during the frame; and specify code parameters for a two-layer code utilized by active transmitters when transmitting during the frame based upon the number of transmitters expected to actively transmit during the frame.

In still another embodiment, the receiver further includes a transmitter configured to transmit control messages that specify code parameters for a two-layer code.

