[0001] The present invention claims priority to U.S. Provisional Patent Application Serial No. 62/646,698 entitled "Coded Random Access Mechanism for Communication Networks" to Farshad Lahouti et al.,filed March 22, 2018, the disclosures of which is herein incorporated by reference in its entirety. FIELD OF THE INVENTION

[0002] The present invention generally relates to communication systems and more specif- ically to communication systems that enable transmission by multiple transmitters on a random access channel. BACKGROUND

[0003] 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.

[0004] 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.

[0005] 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

[0006] 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.

[0007] 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; and

selecting 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; 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; and

wherein 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; and output decoded packets of user data.

[0008] 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.

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

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

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

[0012] 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.

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

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

[0015] 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.

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

[0017] 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. [0018] 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.

[0019] 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.

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

[0021] 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 com- prising 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; and

selecting 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.

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

[0023] 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 trans- mitters 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; and

output decoded packets of user data.

[0024] 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.

[0025] 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.

[0026] 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.

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

BRIEF DESCRIPTION OF THE DRAWINGS

[0028] Figs. 1A and 1B conceptually illustrate a random access system in accordance with an embodiment of the invention.

] Fig. 2A conceptually illustrates a transmitter in accordance with an embodiment of the invention.

[0030] Fig. 2B conceptually illustrates multiple transmitters sharing a random access channel within a two-layer coded access system in accordance with an embodiment of the invention.

[0031] Fig. 3A conceptually illustrates a receiver in accordance with an embodiment of the invention.

[0032] Fig. 3B conceptually illustrates a factor graph of the receiver in the case of using LDPC codes in a code layer with message passing decoding between the code layer and a MAC layer in accordance with an embodiment of the invention.

] Fig. 3C conceptually illustrates a factor graph of a decoder that uses multiple individual decoders in a code layer with message passing decoding between the code layer and a MAC layer in accordance with an embodiment of the invention.

] Fig. 4 presents Table 1, which summarizes the edge and node-perspective degree distributions for decoding graphs of decoders implemented in accordance with various em- bodiments of the invention.

[0035] Fig. 5 conceptually illustrates message passing within a decoder implemented in accordance with an embodiment of the invention.

[0036] Fig. 6 presents Table 2, which shows input load thresholds corresponding to optimized degree distributions for target loads.

[0037] Fig. 7 is a chart showing performance of decoders in accordance with various embodiments of the invention that implement short block-length codes.

[0038] Fig. 8 is a chart showing a comparison of the values of P _E (H) for a (24,14,4) cyclic code with step and linear approximations, respectively.

[0039] Fig. 9 conceptually illustrates message passing during a decoding iteration in accordance with an embodiment of the invention.

[0040] Fig. 10 presents Table 3, which lists the optimized codes and degree distributions using linear approximation and Reed-Muller codes up to length 128.

[0041] Fig. 11 depicts the rate per user performance (b/s/Hz) of the proposed coded access scheme with LDPC codes as a function of the number of active users over the binary adder channel with erasure probability = 0.1.

[0042] Fig. 12 is a chart that depicts the maximized per-user transmission rate for different values of outage probability using the LDPC codes, along with the corresponding outage capacity curves (without complexity constraints).

[0043] Fig. 13 is a chart that shows the performance of the proposed system using LDPC codes as a function of the actual number of active transmitters.

[0044] Fig. 14 is a chart that compares the optimized user rate threshold using the family of Reed-Muller codes for m ^(RM) < 5, with the same system using LDPC codes for = 0.1 ^{and d} _max ^{= 13}

[0045] Fig. 15 is a chart that compares the optimized user rate threshold using exact and approximated values of P _E (H) for Reed-Muller codes with m ^(RM) < 5 for = 0.1 and ^d _max ^{= 13.} DETAILED DESCRIPTION

[0046] Turning now to the drawings, systems and methods for coded access communication in accordance with various embodiments of the invention are illustrated. Systems and methods in accordance with many embodiments of the invention utilize a two-layer codes access scheme when communicating over a binary adder access channel with erasures. As can readily be appreciated, this channel model is also appropriate for binary signaling over a noisy channel, where a received signal with low reliability may be interpreted as erasure.

[0047] Two-layer coded access schemes in accordance with various embodiments of the invention can utilize an inner layer that is intended to resolve collisions and an outer layer that targets erasures. The layers can operate in lockstep while passing messages back and forth, which results in the ability of the receiver to perform joint resolution of collisions and erasures. In a number of embodiments, the communication system is utilized in a multiple access scenario where the number of users within a frame is known at the transmitter and the receiver. In several embodiments, the number of users within a frame is information that is only known by the receiver.

[0048] In many embodiments, the system utilizes a receiver in which the MAC layer and the code layer cooperate by iteratively passing messages back and forth to achieve joint resolution of collisions and erasures. As is discussed further below, the use of message passing within a two-layer access scheme can significantly increase the average per user data rate of the communication system with an acceptable increase in the complexity of the receiver. In many embodiments, the proposed message passing decoder for the two-layer coded access scheme offers a linear complexity as a function of number of users and node degrees and approaches the capacity of the corresponding channels.

] In many embodiments, the code parameters in both layers can be optimized to improve the overall throughput of the communication system. In certain embodiments, one layer isfixed (e.g. a specific error correction code is specified for use in a standard) and the other layer is optimized with respect to thefixed layer. Systems and methods in accordance with various embodiments of the invention are capable of using LDPC and/or short block length codes. Furthermore, the codes employed by the communication system are able to be selected/optimized both for the case of long codes and short (algebraic) codes. In certain embodiments, the receiver coordinates adjustments of the code parameters based upon an observed and/or expected number of active transmitters and/or observed channel conditions. In several embodiments, the adjustments coordinated by the receiver increase channel throughput. In many embodiments, the adjustments increase the average achievable user data rate. In certain embodiments, the adjustments involve selection of code rate parameters from a set of different code rate parameter combinations, where the selection is the optimum selection given the observed and/or expected number of active transmitters and possibly additional constraints.

[0050] In a number of embodiments, the communication system utilizes LDPC codes of large block-length and algebraic codes of short block-length to implement a two-layer access scheme. Optimization of systems that utilize long codes demonstrates the ability to achieve superior performance in comparison to the capacity of an equivalent orthogonal MAC, and other related prior art systems. With an imposed complexity constraint, coding schemes in accordance with various embodiments of the invention that employ large block-lengths such as (but not limited to) LDPC codes: (i) surpass the performance of an equivalent perfect orthogonal transmission scheme; (ii) approach the outage capacity of the binary adder random access channel, and (iii) noticeably outperform previous benchmarks, in which the two layers are designed and operate separately.

[0051] In certain embodiments, short block-length codes can be utilized as an alternative to longer iterative codes. Optimization with short codes can be enabled through the use of an efficient approximation of the decoding performance of a candidate code using its parity check matrix. In the case of algebraic codes of short block-length, the results show that as the number of transmitters increases, their performance gap with codes of large block-length in the context of two-layer coded access schemes rapidly declines.

[0052] Communication systems and methods that utilize two-layer coded access schemes and receivers that employ message passing between a MAC layer and a code layer to enable joint resolution of collisions and erasures in accordance with various embodiments of the invention are discussed further below. Random Access System

[0053] A random access system in accordance with an embodiment of the invention is conceptually illustrated in Figs. 1A and 1B. In many embodiments, a random access (RA) system 100 is utilized including one receiver (base station) 102 and a total of N transmitters 104 that share a communication channel 106. Time on the shared communication channel can be divided into contention frames of length T _f , which include T bit intervals of length T _b , hence T _f = T * T _b . Each transmitter 104 can be considered to participate in a frame with the probability p _a . Under this assumption, each contention frame can be considered to include a random number of active senders. By assuming a large number of transmitters N and a low activity probability p _a , the number of active transmitters in a frame, N _a , can be assumed to follow a Poisson distribution with parameter Np _a . As can readily be appreciated, a variety of probability distributions can be assumed with respect to the number of active transmitters as appropriate to the requirements of specific applications in accordance with various embodiments of the invention.

[0054] The packets transmitted by the transmitters 104 can be variable length or assumed to be of equal size (i.e. k bits) and sent randomly on T available bit intervals in a frame, leading to a common transmission rate of R _t = k/T bits per user per bit interval. In a number of embodiments, each active transmitterfirst encodes its k bit packet into n bits (k < n) and then transmits them over T bit intervals with possible repetitions (T ³ n) according to a random butfixed pattern. Furthermore, self-collisions are not allowed, however, different transmitters can use the same bit intervals. As discussed further below, the manner in which the transmitters 104 encode the user data is determined based upon a two-layer coded access system employed by the communication system 100. The two-layer coded access system enables the receiver 102 to handle both collisions and erasures.

[0055] In several embodiments, the receiver 102 is assumed to know both the set of active transmitters and their transmission patterns (location of their bits) in the frame. Indeed, these transmission patterns may be agreed upon between the transmitters 104 and the receiver 102 in a setup and the receiver can adjust the code parameters based upon changes in the number of active transmitters and/or the channel conditions. Ideas on practical ways to handle such issues are presented in Shirvanimoghaddam, Mahyar, et al. "Probabilistic rateless multiple access for machine-to-machine communication." IEEE Transactions on Wireless Communications 14.12 (2015): 6815-6826, the disclosure of which including the disclosure relevant to techniques for determining a number of active transmitters and/or their transmission patterns at a receiver is hereby incorporated by reference herein in its entirety. In a number of embodiments, the transmitters are only aware of when a new contention frame starts and are unaware of the number of other active transmitters. They do not receive any other feedback from the base station or other transmitters. In practice, frame synchronization in an RA system is typically facilitated by the transmission of beacon messages by the receiver to mark the start of a frame. Accordingly, while not shown in Fig. 1A, each receiver may include a transmitter for broadcasting control messages and each transmitter may include a receiver for receiving control messages and/or adjusting code parameters utilized in the encoding of transmitted data in response to the control messages received from the receiver.

[0056] While various communication systems are described above with reference to Fig. 1, any of a variety of communication systems that employ a RA channel can be utilized as appropriate to the requirement of specific applications in accordance with various embodiments of the invention. In much of the discussion that follows, the operation of systems and methods in accordance with various embodiments of the invention is considered in the context of bit intervals and bit transmissions. Systems and methods in accordance with many embodiments of the invention can, however, operate in a more general manner involving time- slots, bit sequences, and/or symbols. Furthermore, as can readily be appreciated, systems and methods in accordance various embodiments of the invention can also be utilized within a communication system in which the number of active transmitters is known to one or more of the transmitters within the communication system. Prior to discussing transmitters and receivers employed in communication systems that employ two-layer coded access systems in accordance with various embodiments of the invention, however, an overview of the a binary adder random access channel model is discussed below. Binary Adder Random Access Channel Model [0057] The operation of systems and methods in accordance with many embodiments of the invention can be considered in the context of a binary adder random access channel with erasures, with output r Î {0, 1, 2, ... , N _a } È {e} given by

where, as before, N _a is the (random) number of active transmitters in a frame, x _i Î {0, 1}, 1 £ i £ N _a , are the input bits, and e designates an erasure. This simple channel models the situation in which a digital encoder and decoder communicate over an analog channel via modulator/demodulator; the modulator converts bits to analog signals under a power constraint; and the demodulator, having observed a sum of the signals from all the transmitters and a random thermal noise, digitizes it by simple quantization. If the demodulator deems the received signal too noisy to digitize reliably, it declares an erasure and passes it on to the coding layer to resolve.

[0058] For concreteness, consider BPSK modulation in the proposed coded random access setting. In high SNR regime with N _a users, the output of the demodulator r¯ is in {-N _a ,-N _a + 2, ... , N _a - 2, N _a }. A simple transformation r = (r¯ + N _a )/2 converts the received signal in each slot to r Î {0, 1, 2, ... , N _a }. As described above, in presence of noise, the received signal can be considered as erased when the demodulator cannot reliably detect the received symbol; hence we have r Î {0, 1, 2, ... , N _a } È {e}. This is precisely the binary adder channel model presented in (1). For QPSK, as an example of higher order modulations, real and imaginary parts can be treated as in the BPSK case, with one variable node and one time node now dedicated to real and imaginary parts of the received symbols at the decoder. Accordingly, as can readily be appreciated, systems and methods in accordance with various embodiments of the invention are not limited to specific modulation schemes. [0059] Regardless of the number of active users N _a , due to the symmetry of the channel in (1), its capacity-achieving distribution is Bernoulli(1/2), and the sum-rate capacity (for N _a active users) is

[0060] If the number of active users N _a is random but stays constant within a contention frame, the outage capacity is an appropriate performance measure:

where p is the outage probability, i.e. the probability that the system cannot support the target rate R _t given the randomness in the number of active users N _a . While two-layer coded access schemes in accordance with various embodiments of the invention can be utilized within and optimized for other channels, the channel model described above is helpful in evaluating the performance of communication systems that utilize two-layer coded access schemes in accordance with various embodiments of the invention in real world RA channels. Two-layer Coded Access Scheme

[0061] As noted above, systems and methods in accordance with many embodiments of the invention employ a two-layer coded access scheme including a receiver front-end dealing with collisions and an error correcting code dealing with erasures. These two layers run iteratively and update each other, enabling joint contention resolution and decoding of messages. The front-end of the receiver can be referred to as the MAC layer and the error correcting code can be referred to as the code layer. As is discussed below, a variety of options exists with respect to the implementation of the MAC layer and the coding layer including (but not limited to) the choice of the particular type/block length of the code employed within the coding layer. Encoder/Transmitter

[0062] A transmitter 200 in accordance with an embodiment of the invention is conceptually illustrated in Fig. 2A and includes an encoder 202 and a modulator 204. As noted above, a transmitter may also include a receiver (not shown) for receiving command messages from the receiver that coordinate the codes and/or code parameters employed by the encoder 202. The encoder 202 encodes user data in accordance with the two-layer coded access system utilized by a communication system and the modulator 204 modulates the encoded bits for transmission by a shared RA communication channel.

[0063] Fig. 2B conceptually illustrates multiple N _a encoders that are utilized to transmit data using N _a modulators over a random access channel within a two-layer coded access system and a demodulator, which produces the received digits r1, ... , r _T , in accordance with an embodiment of the invention. With specific regard to the jth sender, the encoder uses an error correcting code with rate R _c = k/n to encode its k-bit packet x ^(j) to create n coded bits c ^(j) . Then for each coded bit the transmitter independently of

previous choices generates a random repetition rate according to the probability mass function {G}. Afterwards, a subset of out of T bit intervals are randomly selected, and each coded bit is sent on different intervals of this set. Each transmitter

uses a bit interval at most once in a frame. The MAC layer rate can be defined as R _m = n/T . Therefore, the common per-user rate R _t can be expressed in terms of code and MAC layer rates: From (1), it is clear that the received value on a bit interval is the summation of coded bits sent on that interval from different transmitters, which could be erased with probability .

[0064] In a number of embodiments, a low-density parity check (LDPC) code from the ensemble C(n, l, r) with design rate of R _c for the code layer is utilized to encode the encoded bits. Refer to Table 1 for definition of parameters. As can readily be appreciated, other iterative error correcting codes canfit the two-layer framework. On the other hand, in delay-sensitive applications, or in the presence of processing power constraints, using long codes is not feasible. In general, many applications in machine-type communications and IoTfit this case. Therefore, systems and methods in accordance with many embodiments of the invention optimize the proposed two-layer system using an ensemble of classic linear block codes for the code layer. In light of various constraints specific applications can place upon the code layer, communication system in accordance with various embodiments of the invention can employ any code appropriate to the requirements of a given application. The selection of the code parameters for two-layer coded access systems that utilize different exemplary codes in accordance with various embodiments of is invention are discussed further below. Decoder/Receiver

[0065] As mentioned earlier, the receiver includes a front-end for contention resolution and channel decoders for dealing with erasures imposed by the channel. Message passing is performed on the decoder’s factor graph to recover the value of the variable nodes. A receiver 300 in accordance with an embodiment of the invention is conceptually illustrated in Fig. 3A. The receiver includes a demodulator 302, which demodulates received signals and a decoder 304 that is responsible for decoding and outputting user data bits using knowledge of the two-layer coded access scheme utilized by the communication system. As noted above, the receiver may also include a transmitter (not shown) for broadcasting control messages including (but not limited to) beacon messages to synchronize frames and code parameter coordination messages used to adapt the codes and/or code parameters/rates utilized to transmit data within the communication system.

[0066] Fig. 3B conceptually illustrates a factor graph of the receiver in the case of using LDPC codes with message passing decoding. Fig. 3C conceptually illustrates a factor graph of the receiver using classic codes with MAP decoding and message passing. In many embodiments, messages passed on the edges of the decoder’s graph are either e, meaning the value of the variable node has not been recovered yet, or they are 0 or 1, reflecting the value of the associated variable node.

[0067] For each node in a layer, a node-perspective and an edge-perspective degree distribution can be defined. The former determines the fraction of nodes with different degrees, while the latter specifies the fraction of edges connected to nodes with specified degrees. Polynomial representation of a node-perspective degree distribution A = {A0, A1, · · · , A _d } can be defined as while for an edge-perspective degree distribution

a = {a1, a2, · · · , a _d }, the polynomial form can be expressed as a

addition, the edge-perspective polynomial can be obtained by the normalized derivative of the node-perspective polynomial. Table 1 shown in Fig. 4 summarizes the edge and node-perspective degree distributions for the decoding graph.

[0068] The processing rule at a time node of degree d with input messages m _i , 1 i d

and a received value of r is

ì

Equation (5) states that a time node can recover the unknown bits whenever there is no other choice for them except being all zeros or all ones. Note that the message sent from an erased time node is always e.

[0069] For the code layer, depending on the application, LDPC codes or short linear block codes can be used. While a variety of encoder and decoder configurations are described above with respect to Figs. 2A - 3C, any of a variety of transmitters and receivers can be utilized within communication systems in accordance with various embodiments of the invention according to the requirements of specific applications and/or the MAC and/or coding layers employed within the two-layer coded access scheme employed within the communication system. Using LDPC Codes

[0070] Fig. 3B shows the factor graph 350 of a decoder that utilizes LDPC codes in accordance with an embodiment of the invention, which can be obtained by combining N _a Tanner graphs of the senders’ LDPC codes to the transmission graph of the coded bits. Both layers use message passing decoding on bipartite graphs. Check nodes of the LDPC Tanner graphs (designated by squares) and time nodes (triangles) are the function nodes, and bit nodes (circles) are the variable nodes in this graph.

[0071] The N _a LDPC decoders behave in a manner similar to standard erasure decoders, i.e., the output message of a check node equals the modulo-2 sum of its input messages, if none of them is e.

[0072] On the other hand, since the erasure channel does not change received values but erases them, the non-erased input messages to a bit node are expected to agree. Therefore, when the value of a bit node is recovered from a time node or a check node equation, it equals the real value sent by the transmitter. As a result, the outgoing message from a variable node is e if all the input messages are erased; otherwise, it equals the same non-erased value of the input messages.

[0073] While the discussion above relates to LDPC codes, as can readily be appreciated, any of a variety of iterative and/or capacity approaching codes can be utilized to implement a two-layer access system as appropriate to the requirements of specific applications in accordance with various embodiments of the invention. Using Short Classic Codes

[0074] Fig. 3C conceptually illustrates the factor graph 375 of a decoder that uses N _a individual decoders for the code layer in accordance with an embodiment of the invention. The architecture in general can accommodate different individual decoders for the short codes. In several embodiments, block map decoders are utilized. As can readily be appreciated any of a variety of codes appropriate to the requirements of a specific application can be utilized. In the illustrated embodiment, each Maximum A Poteriori (MAP) decoder, depending on the erasure pattern of the input codeword, either recovers all the erased bits or fails to recover any of them. As can readily be appreciated, any of a variety of decoders can be utilized to recover erased bits as appropriate to the requirements of a given application. Design, Operation and Complexity Considerations

[0075] As the transmitters select bit intervals based upon a code design that specifies a transmission pattern known to the receiver, the time node degree distribution {Y} cannot be designed directly and is obtained from repetition rate distribution of variable nodes, i.e., {G}. In many instances, the selected repetition rates and/or transmission pattern are determined based upon the channel characteristics of the random access channel and/or any other factors relevant to a particular application.

[0076] The probability that the jth transmitter selects a bit interval is d ^(j) /T , where is the total number of transmissions for sender j. As the code length grows,

according to the law of large numbers:

where G(.) is the polynomial representation of the repetition rate distribution. Hence, the degree of time nodes follows a binomial distribution: ( )

[0077] With LDPC codes, the decoding complexity is determined by the total number of edges in the decoder’s graph, as the number of operations at each node has a linear relationship with its degree. The number of edges in the code layer and the MAC layer graph are n respectively. Hence, the complexity of decoding in

one iteration is Overall, for the proposed

decoder, the complexity remains linear in terms of the number of active users, code length and maximum degree of nodes. In the case of short codes, the decoding complexity depends on that of the individual decoders. Still the share of the complexity due to the MAC layer remains the same.

[0078] A specific setting in this architecture, for N _a = 2 and R _m = 1, known as two- user joint iterative decoding, is discussed in academic literature for Gaussian and binary adder multiple access channels. This is equivalent to code design for afixed transmission scheme. In general, the proposed two-layer architecture introduces an additional degree of freedom in system design and enables joint optimization of the code and transmission strategy. This in turn provides wider design trade-offs for complexity and user and system rate and performance,which are discussed further below.

[0079] In a number of embodiments, the definition of the decoder isfinalized by the specification of a schedule. In many decoders, a decoding iteration starts with the MAC layer; the time nodes send their values to the variable nodes. Then a decoding round at the code layer is performed, where the variable nodes send their updated values to the check nodes (case of LDPC) or to the (MAP) decoders (case of short codes) and receive the answers. The variable nodes send their updated values to the time nodes. This concludes a decoding iteration. The decoder can continue to iterate until a stopping criterion is reached such as (but not limited to) either no new bit node is recovered during an iteration, or a maximum number of iterations is reached. Asymptotic Analysis of Decoding Threshold - LDPC Codes

[0080] Like other message-passing decoders, decoders in accordance with various embodi- ments of the invention exhibit threshold behaviors for infinitely large code and frame lengths. The threshold can be determined both by the channel erasure probability and the input load. More accurately, under the assumption of asymptotically large code and frame length, if the number of active transmitters does not exceed N ^*

a and the erasure probability is less than ^* , the receiver is able to recover message bits completely as long as the per-user rate is less than the threshold, . An equivalent characterization of the decoding threshold is the

maximum load sustainable by the system that is compatible with a given rate and erasure probability, The decoding performance of the receiver can be analyzed in an

asymptotic setting. Density evolution (DE) offers a tool to calculate the average performance of a code ensemble in each iteration under the assumption of infinite code length. Under this assumption, the decoding graph becomes a tree, which implies the independence of incoming messages to a node. In order to conduct the analysis, the erasure probability transfer function of each node is derived. Then, a set of equations is introduced to recursively track the erasure probability in each iteration. Erasure Transfer Function of Nodes

[ ^{0081] The probability P} _out ^{that the output message of a node equals e can be found given the erasure probability of input messages p . Under the assumption of infinite code} and frame lengths, all messages entering a node are independent, since there is no loop in the decoding graph of the receiver.

[0082] From the standard density evolution of erasure correcting LDPC codes, the following can be obtained for the check and variable nodes:

[0083] For time nodes with the processing rule in (5), Proposition 1 presents the transfer function. Proposition 1. Erasure transfer function of a time node is described by Tracking Decoder Erasure Probability

[0084] Having derived the erasure probability transfer function of the nodes, the erasure probability of a specific message along different iterations forfixed N _a and can be tracked. This is done by stating the erasure probability of a message in terms of its value in the previous iterations. In the following, the message sent from the node a to the node b in the ^th iteration is denoted is the probability that quals Î, where a and b

can stand for v (for variable nodes), c (for check nodes), and t (for time nodes).

[0085] Fig. 5 demonstrates the messages passed in one iteration to update By expressing the erasure probability of each message in terms of the erasure probability of its generating messages, a set of recursive equations for can be obtained:

Equations (12) and (14) are derived from (10), while (13) and (15) are based on (11) and (9), respectively. The definition of the initial values for the recursion in (16) and (17) can be obtained since at the beginning of the decoding, every variable node is unknown and all edges carry erasure messages. Note that in each iteration, the fraction of non-recovered variable nodes is given by

Optimizing Degree Distributions

[0086] One can determine for afixed N _a and , byfinding the largest value of

R _t which leads to a zero convergence value for in recursion (12) to (16). This could be done using a binary search on R _t .

[0087] An analysis can be performed with respect to the optimized degree distributions that lead to the largest per-user rate threshold for afixed channel erasure probability ^* and maximum number of active transmitters

[0088] The second constraint limits the total number of transmissions per user so that it does not exceed T , as users cannot use a bit interval more than once in a frame. Differential evolution is described in Storn, Rainer, and Kenneth Price. "Differential evolution a simple and efficient heuristic for global optimization over continuous spaces." Journal of global optimization 11.4 (1997): 341-359, the disclosure of which including the relevant disclosure related to systems and methods for performing differential evolution is hereby incorporated by reference herein in its entirety. Differential evolution processes can be utilized to solve the above optimization problem. This meta-heuristic method, which is a combination of hill climbing and genetic algorithms can be utilized since it is capable of searching large parameter spaces effectively. As can readily be appreciated, any of a variety of processes can be utilized to solve the optimization problem as appropriate to the requirements of a given application. [0089] The design procedure is as follows: By having the acceptable outage probability and the average number of active transmitters Np _a , the maximum

number of tolerable senders is determined. Then, by solving (19) one can calculate the

optimized degree distributions leading to the maximum per-user transmission rate.

[0090] Table 2 shown in Fig. 6 presents the input load thresholds corresponding to o ^{ptimized degree distributions for target load and different values of Î for d} _max

limited to 13. As expected, as the probability of channel erasure grows, the code rate decreases to cope with channel impediments. In many embodiments, processes similar to those described above can be utilized to develop rate tables and/or sets of code parameters that are utilized by active transmitters in response to control messages generated based upon estimates of the number of active transmitters by the recever.

[0091] Another observation from Table 2 is the abundance of degree-2 variable nodes in the code layer (l2 = 1). Such result is expected since rate threshold is the sole subject of maximization in (19). The number of degree-2 variable nodes plays a major role in the trade-off between errorfloor and the threshold. For that matter, one can consider constraining l2 in (19) to trade the rate threshold for errorfloor.

[0092] In the noiseless case ( = 0), the optimization results in the highest code rate possible (in the presence of constraint on maximum node degree). This suggests that, in the noiseless scenario, by removing the code layer a better performance could be achieved. However, when the channel erasure exists, the MAC layer alone cannot recover all the transmitted bits. Proposition 2 introduces a lower bound on the fraction of non-recovered bits for the MAC layer.

Proposition 2. By having only the MAC layer, the fraction of non-recovered bits is lower- bounded by G( ).

Proof. The MAC layer cannot recover a bit node if all its repetitions on the channel have been erased. All transmissions of a degree d bit node will be erased by the channel with probability ^d . By averaging over d:

Therefore, the probability of erasing all transmissions of a bit is G( ). [0093] As can readily be appreciated, there is a trade-off depending upon the selection of the code rate: on one hand, a low code rate increases the correction capability of the code layer, but on the other hand, it raises the load on the MAC layer, increasing the collisions and the risk of decoding failure. Asymptotic Analysis of Decoding Threshold - Classic Linear Block Codes

[0094] The equations for erasure transfer functions of time and variable nodes are outlined above. To incorporate the performance of block MAP decoders into the analysis of a communication system that utilizes a two-layer access control system in accordance with an embodiment of the invention, the erasure transfer function of the MAP decoders can be derived. More specifically, the probability of decoding failure, given the i.i.d. erasure probability of codeword bits, is developed.

[0095] The set of indexes of erased and non-erased elements in a codeword can be defined as E and E¯ Í {1, 2, ..., n}, respectively. In addition, cE is defined as the sub-vector of erased elements in c, and HE as the sub-matrix composed by selecting corresponding columns of H ^{in the set E . For a linear block code C(n, k, d} _min ^{) with the parity check matrix H, c is a} codeword if and only if Hc ^T = 0. This can be restated as

[0096]

[0097] Since s is known at the decoder, every codeword c satisfying (20) could be the MAP decoded codeword with equal probability. Therefore, for the decoder to be successful in retrieving all the erasures, the system of equations in (20) should lead to only one answer. This is equivalent to HE having a full column rank. In other words, the block MAP decoding is successful if and only if

[ ^{0098] With i.i.d. erasure probability of p} _in ^{for elements of a codeword, the probability of} MAP decoding failure P _e can be derived as follows

where ^test is an indicator function, which is 1 when the test is satisfied and zero otherwise. Le we have

[0099] P _E (H) can be considered as the ratio of the number of sub-matrices of H with non-complete column rank to the total number of sub-matrices of H with E columns:

[0100] In fact, P _E (H) is the probability of decoding failure in case of having E erasures in ^{a codeword. The probability of having E erasures with erasure probability p} _in ^{in a codeword of length n can be defined as as follows:}

Therefore, the probability of decoding failure can be stated as follows

[0101] Having P _E (H) values of a linear block code for 0 £ E £ n, one can determine the performance of the code under i.i.d. erasures using (24). In fact, P _E (H) characterizes the ^{erasure correction capability of the code, and p} _E ^(p _in ^{)represents the erasure imposed by the} channel.

[0102] Fig. 7 shows P _E (H) coefficients for a (24,14,4) code and a (16,11,4) Reed-Muller ^{(RM) code, as well as p} _E ^(p _in ^{)for different values of p} _in ^{. It is evident in thisfigure and also (24) that when the overlap of non-zero values of P function of E) is} smaller, the erasure correction performance of the code is stronger.

[0103] Exact computation of P _E (H) is only feasible for short codes as it demands O(2 ⁿ n ³ ) operations. This is when Gaussian elimination can be used with O( operations tofind the rank of 2 ⁿ matrices corresponding to each erasure pattern. However, a few simplifying factors can be considered without departing from the scope of the invention. First, every linear block ^{code is capable of correcting all erasure patterns of weight d} _min ^{- 1 or less. In addition, the} rank of a parity check matrix (and all its sub-matrices) are at most n - k. Therefore,

^{[0104] As a result, only needs to be computed for d}

_min ^{£ E £ n - k, which} is still complicated for long or low-rate codes. An alternative approach is to approximate P _E (H). Equation (28) demonstrates a step approximation which assumes the code can only ^{correct erasure patterns of weight less than d} _min ^{. In fact, this approximation is accurate for} a decoder whichfirst replaces the erasures randomly from the alphabet (zeros and/or ones for binary codes), and then performs bounded distance decoding.

[ ^{0105] In the same direction, a linear approximation of can}

also be considered:

[0106] Fig. 8 compares the values of P _E (H) for a (24,14,4) cyclic code with step and linear approximations in (28) and (29), respectively. It can be seen that the approximations are more accurate for codes whose minimum distance approaches n - k. In fact, it is most accurate when the code is MDS. It is also evident that the approximations offer lower bounds on code performance, and can be used for optimizing the system. Tracking Decoder Erasure Probability

[0107] In the previous section, the probability of block MAP decoding failure is charac- terized. The evolution of erasure probability of a certain message can be tracked through different iterations for afixed N _a and in the proposed two-layer decoding architecture of Fig. 3C. Fig. 9 demonstrates the messages passed in one iteration to update m _ct . By expressing the erasure probability of each message in terms of the erasure probability of its generating messages, a set of recursive equations for can be obtained. Using bit and time node

erasure transfer functions from (10) and (11), the following can be obtained

[0108] From (24),

[0109] Since at the beginning of the decoding, every variable node is unknown and all edges carry erasure messages, the initial value for the recursion is

[0110] Unlike a decoder that employs iterative codes such as (but not limited to) LDPC codes, where large code lengths allow for asymptotic analysis, for density evolution equations (30) to (32) to be valid an assumption of a large number of active users in each frame N _a is needed to conform to the asymptotic regime. Optimizing Code and Repetition Rate Distribution

[0111] Using the recursive set of equations in (30)-(33), the user rate threshold R ^*

t can be computed corresponding to a repetition rate distribution {G}, parity check matrix H , number of active transmitters N _a , and channel erasure probability . Considering the thresholding behavior of the decoder, if for a specific user rate R _t the convergence value for in equations (30) to (33) (P ^(¥)

c _t ) is positive, then On the contrary, a zero value of

for a user rate implies that R As such, a binary search can be performed

on R ^*

t to calculate the user rate threshold for afixed N _a and .

[0112] Based upon the above results, a search can be performed for the pair of an optimized code and repetition rate distribution; i.e., the optimized code is selected from the ensemble along with an optimized degree distribution {G}.

Furthermore, C could be part of a code family, e.g., Reed-Muller codes, Hamming codes, and Expander codes, or in general, it could be a set of arbitrary binary linear block codes. The

pair can be solved by solving the following optimization using Differential Evolution.

[0113] Table 3 shown in Fig. 10 lists the optimized codes and degree distributions using linear approximation and Reed-Muller codes up to length 128 as the ensemble C. It is evident that with a larger number of users, the system tries to reduce collisions by increasing the portion of the bit nodes with only one repetition. Simulation Results

[0114] Numerical and simulation results can be utilized to analyze the performance of communication systems that utilize two-layer coded access schemes over a binary adder channel with erasures in accordance with various embodiments of the invention. First, a multiple access setting is considered, where the number of active users N _a is known both at the transmitters and the receivers. Next, a random access scenario is considered, where the number of active users is random in each frame and only known at the receiver. Multiple Access Channel

[0115] Fig. 11 depicts the rate per user performance (b/s/Hz) of the proposed coded access scheme with LDPC codes as a function of the number of active users over the binary adder channel with erasure probability = 0.1. The performance is obtained by solving the ^{design optimization problem (19) for each}

[0116] For comparison, the capacity of the multiple access channel is also presented, and the multiuser capacity with orthogonal transmission. As evident, the proposed scheme noticeably outperforms an ideally coded orthogonal transmission scheme.

[0117] Of interest is also a comparison with a complexity-constrained capacity of a binary adder MAC with erasure. Suppose that due to complexity constraints, only K-fold (K < N _a ) collisions over each time-slot are allowed. The sum-rate capacity of an adder erasure MAC with a K-fold constraint is given by (2) as C _K . Furthermore, suppose that the complexity constraint is expressed in terms of time-node degree distribution where

y _k represents the fraction of time nodes of degree k. The sum-rate capacity of adder MAC with time-node degree distribution constraint is given by

[0118] It can be seen in Fig. 11 that the proposed scheme has a small performance gap with the (constrained or unconstrained) MAC capacity. This performance is obtained with the proposed sub-optimal decoder whose complexity grows only linearly with the number of users, code length and maximum degree of nodes. Random Access Channel

[0119] For different maximum numbers of active transmitters N optimized random access

codes can be designed by solving (19) and (34). Translating the maximum number of active transmitters into target outage probabilities for a Poisson distribution of number of active users, the performance of the system for different average input loads, Np _a can then be simulated.

[0120] In simulating the code layer, the LDPC codes are constructed randomly from optimized degree distributions by avoiding cycles of size 4. Although more advanced code construction methods can be considered for practical implementation. For the classic linear block codes, the family of Reed-Muller codes can be used as the search space C in the optimization problem (34). Reed-Muller codes offers a class of highly structured linear block codes with predefined minimum distances. This is important in the current setting, since it allows performance of the code family to be characterized using the approximations (28) and (29) simply by the code parameters m ^(RM) and r ^(RM) .

[0121] Fig. 12 demonstrates the maximized per-user transmission rate R _t for different values of outage probability using the LDPC codes, along with the corresponding outage capacity curves (without complexity constraints). The proposed design noticeably outperforms the outage capacity of orthogonal signaling (computed by letting C _Na = 1 - in (3)), confirming that indeed allowing collisions in this framework is beneficial. Furthermore, performance of two-layer coded access schemes is compared with a benchmark system, in which the MAC layer is optimized for a non-erasure channel and the code layer is an LDPC code designed for the BEC( ). Unlike a system in accordance with an embodiment of the invention that utilizes a two-layer access control system in which the MAC layer and the code layer cooperate by iteratively passing messages back and forth to achieve joint resolution of collisions and erasures, the two layers in the benchmark scheme operate in tandem. One sees that the proposed scheme noticeably outperforms the benchmark and approaches the corresponding outage capacity curves. Also evident is a rather graceful trade-off of quality of service (quantified by probability of outage) and throughput performance (achievable rate). A more stringent QoS constraint imposes a greater toll on throughput.

[0122] Fig. 13 shows the performance of the proposed system using LDPC codes as a function of the actual number of active transmitters. Although the curves in Fig. 13 are evaluated for limited code and frame lengths, in line with the asymptotic analysis described above, the system exhibits a threshold effect at the designed maximum number of active senders,

[0123] Fig. 14 compares the optimized user rate threshold using the family of Reed-Muller ^{codes for m(RM) < 5, with the same system using LDPC codes for ^ = 0.1 and d} _max ^{= 13.} Exact performance of the RM codes (P _E (H)) has been used to design the system (solving (34)). As shown in thefigure, by increasing the average number of active transmitters Np _a , the performance gap between the short and long codes decreases.

[0124] Fig. 15 compares the optimized user rate threshold using exact and approximated ^{values of P} _E ^{(H) for Reed-Muller codes with m(RM) < 5 for ^ = 0.1 and d} _max ^{= 13. As} expected, compared to the step approximation, optimized rates using linear approximation are closer to those based on exact values of P _E (H). In fact, the codes selected in the optimization process for linear approximation and exact P _E (H) are the same. Also, the optimized degree distributions resulted from both approaches are very similar.

[0125] Although the present invention has been described in certain specific aspects, many additional modifications and variations would be apparent to those skilled in the art. It is therefore to be understood that the present invention can be practiced otherwise than specifically described including any of a variety of short and long block length codes including capacity approaching codes and/or other iterative codes that can be decoded in a two layer access system using message passing and/or communication systems that operate over other types of multiple access communications channels without departing from the scope and spirit of the present invention. Thus, embodiments of the present invention should be considered in all respects as illustrative and not restrictive. Accordingly, the scope of the invention should be determined not by the embodiments illustrated, but by the appended claims and their equivalents.