Achievability Bounds for T-Fold Irregular
Repetition Slotted ALOHA Scheme in the Gaussian
Multiple Access Channel
Nikolay Matveev‡, Kirill Andreev∗, Alexey Frolov∗† and Andrey Turlikov

‡

∗ Skolkovo Institute of Science and Technology

Moscow, Russia

† Institute for Information Transmission Problems

arXiv:1802.07332v1 [cs.IT] 20 Feb 2018

Russian Academy of Sciences
Moscow, Russia
‡ State University of Aerospace Instrumentation, St. Petersburg, Russia
n.matveev@vu.spb.ru, k.andreev@skoltech.ru, al.frolov@skoltech.ru, turlikov@vu.spb.ru

Abstract—We address the problem of massive random access
for an uncoordinated Gaussian multiple access channel (MAC).
The performance of T-fold irregular repetition slotted ALOHA
(IRSA) scheme for this channel is investigated. The main difference of this scheme in comparison to IRSA is as follows: any
collisions of order up to T can be resolved with some probability
of error introduced by Gaussian noise. First, we generalize the
density evolution method for T -fold IRSA and noisy channel
and find optimal degree distributions for different values of T .
Then we perform analysis and find minimal Eb /N0 for a fixed
length, rate and packet loss probability. The scheme is shown to
work closer to finite length random coding bound proposed by
Y. Polyanskiy, than existing solutions.

I. I NTRODUCTION
Existing wireless networks are designed with the goal of
increasing a spectral efficiency in order to serve human users.
Next generation of wireless networks will face a new challenge
in the form of machine-type communication. Analysts predict
that the number of devices connected to the network will
exceed 50 millions by 2020. The main challenges are as
follows: (a) huge number (billions) of autonomous devices
connected to one access point, (b) low energy consumption,
(c) short data packets. This problem has attracted attention of
3GPP standardization committee under the name of mMTC
(massive machine-type communication).
Let us describe the system model. There are Ktot ≫ 1
users, of which only K are active in each time instant.
Communication proceeds in a frame-synchronized fashion
(this can be implemented with use of beacons). The length
of each frame is n. Each active user has k bits to transmit
during a frame. The main goal is to minimize the energy-perbit spent by each of the users. We are interested in grant-free
access (5G terminology), i.e. active users transmit their data,
without any resource requests.
This paper deals with construction of low-complexity random coding schemes for the Gaussian multiple-access channel

(GMAC) with equal-power users, i.e.
y=

Ktot
X

si xi + z,

(1)

i=1

where xi ∈ Rn is a codeword transmitted by the i-th user, si
is an activity indicator for the i-th user, i.e. si = 1 if the i-th
user is active and si = 0 otherwise. z ∼ N (0, I) is an additive
white Gaussian noise (AWGN). Following [1] we assume all
the users to use the same message set [M ] , {1, . . . , M } and
the same codebook C = {x(ω)}M
ω=1 of size M . Let ωi denote
the message of the i-th user. To transmit the message ωi the
user will use a codeword xi = x(ωi ). We require in addition
that ||x(ω)||22 ≤ nP , which means a natural power constraint.
Decoding is done up to permutation of messages. We only
require the decoder to output a set L(y) = (ω1 , ω2 , . . . , ωJ ) ∈
[M ]J , J ≤ K. Thus in accordance to [1] we decouple the user
identification problem and the data transmission problem. The
probability of error (per user) is defined as follows
Pe =

max

|(s1 ,s2 ,...,sKtot )|=K

Ktot
1 X
si Pr(Wi 6∈ L(y)).
K i=1

Let us emphasize the main differences from the classical
setting. Almost all well-known low-complexity coding solutions for the traditional MAC channel (e.g. [2]) assume
coordination between the users. Due to the gigantic number
users we assume them to be symmetric, i.e. the users use the
same codes and equal powers.
We continue the line of work started in [1], [3], [4]. In
[1] the bounds on the performance of finite-length codes
for GMAC are presented. In [3] Ordentlich and Polyanskiy
describe the first low-complexity coding paradigm for GMAC.
The improvement (it terms of required Eb /N0 ) was given
in [4]. The overall scheme can be called T-fold irregular
repetition slotted ALOHA (IRSA, [5], [6]) scheme for GMAC.
The main difference of this scheme in comparison to IRSA is
as follows: any collisions of order up to T can be resolved
with some probability of error introduced by Gaussian noise.

users

+

+

+

+

In this paper we investigate the potential capabilities of T fold IRSA. The authors of [4] suggested to split the error
probability into three terms: interference cancellation (IC)
error, preamble error and decoder error. Then a union bound
was applied. We were able to write joint density evolution
rules, which include all the terms. In what follows we show,
that this change allows us to better predict the error probability.
We also note the following thing. In [4] in each slot preambles
were used to identify active users. So the packet consists of
preamble and data part. The authors used finite length random
coding bound [1] to estimate the probability of decoding
failure in the data part. We emphasize, that preambles are
not needed to characterize the potential capabilities (derive
achievability bounds) of T -fold IRSA scheme as we do not
need to identify users, that are active in a slot to use IC
algorithm.
Our contribution is as follows. Achievability bounds for T fold IRSA are derived. To achieve this goal we generalized the
density evolution method for T -fold IRSA and noisy channel
and find optimal degree distributions for different values of T .
Then we perform analysis and find minimal Eb /N0 for a fixed
length, rate and packet loss probability. The scheme is shown
to work closer to finite length random coding bound proposed
by Y. Polyanskiy, than existing solutions.

slots

Fig. 1: Tanner graph representation

The algorithm stops when all the slots are either decoded or
empty (see Algorithm 1 for more details).
Algorithm 1 Interference cancellation decoder
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

while slot set not empty do
Remove empty slots
Select slot with the minimal collision order t
if t ≤ T then
Resolve the collision
Subtract decoded packets from all the slots
Update collision indices for all slots
end if
Remove decoded slot from slot set
end while

II. P RELIMINARIES
A. System model
The main features of the scheme are as follows:
• transmission is performed in a frame-synchronized fashion. The length of a frame is n channel uses;
• the frame consists of M slots of size ñ = n/M channel
uses;
• the user chooses a message ω, then encodes it and obtains
a codeword x(ω) of length ñ;
• users repeat their codewords in multiple slots. The distribution of the repetition count is denoted by D[i]. This
distribution is the same for all the users;
• the number of repetitions r and the r slots in which to
send are chosen based on the message ω (see [4]): as
ω is distributed uniformly on [M ] the slots are chosen
uniformly at random (definitely without repetitions) from
M existing slots.
B. Interference cancellation decoder
Decoding algorithm is based on successive cancellation approach. The algorithm is iterative. The slot with the minimum
collision order is selected at every step. If the order of collision
is less or equal to T we resolve the collision. As a result some
messages (in collision) are decoded successfully, some of the
messages are decoded incorrectly. Then all successfully decoded messages are removed from other slots (if the message
was transmitted by user more than once), the slot itself is
marked as resolved and collision indices are updated for all
other slots. We note, that we can always find where the replicas
were transmitted as these positions are chosen based on the
data (so in contrast to [5] we do not need to store the pointers).

Remark 1: We note, that during the slot decoding the errors
may occur, i.e. some of the packets (codewords) may be
decoded incorrectly. In what follows we assume, that we can
always detect the error packets (the packets include control
information).
C. Tanner graph representation
The transmission and decoding processes can be described
with the use of a bipartite graph, which is called the Tanner
graph [7]. The vertex set of the graph consists of the set of
user nodes V = {v1 , v2 , . . . , vK } which correspond to the set
of users and the set of slot nodes C = {c1 , c2 , . . . , cM } which
correspond to signals received in slots. The user node vi and
the slot node cj are connected with an edge if and only if the
i-th users transmitted a packet in the j-th slot.
D. Degree distributions
P
P
i−1
i
denote the
Let L(x) =
i λi x
i Li x and λ(x) =
user node degree distributions from node and edge degree
perspective, respectively. We recall (see e.g. [8]), that Li and
λi denote respectively the fractions of user nodes of degree i
and the fraction of edges incident to user nodes of degree i.
′
Also recall, that λ(x) = L′ (x)/L
(1). In our case L
Pi = D[i].
P
i−1
i
Analogously, let R(x) =
i ρi x
i Ri x and ρ(x) =
denote the slot node degree distributions from node and edge
degree perspective, respectively.
Let G = K/M . Let us consider the j-th slot. Each
user chooses ′ this slot ′for transmission independently with
probability LM(1) = GLK(1) . Thus,the slot node
 distribution
GL′ (1)
. In the limit
(from node perspective) is Bino K, K

K → ∞ this distribution becomes a Poisson distribution. In
′
what follows we use R(x) = ρ(x) = e−GL (1)(1−x) .

xℓ

xl

yl+1

User
node

III. D ENSITY EVOLUTION

we note, that L′ (1) is actually the average number of transmissions.
Let us introduce a notation. By Pe (ñ, k, P, t) we denote
the error probability per user, calculated with use of random
coding bound [1]. Now let us write the density evolution
rules. By xl and yl we denote the probability that an outgoing
message from the user node and slot node, respectively, are
erased during the l-th iteration. We start with initial condition
x0 = 1, which means, that the user messages are erased at the
beginning and we observe only the noisy signal sums in slots.

…
xl

xl

r-1

…
yl

i

…

i-1

yℓ

xl

yl

yℓ

yℓ

yl

Fig. 2: Density evolution rules
16
Random coding bound
Reference T = 2
Reference T = 4
10 decoding iterations
100 decoding iterations

14
12

T=1
T=2

10

Eb/N0, dB

Following [1] we want to minimize the required energy-perbit Eb /N0 . For this purpose we suggest a density evolution
method, which helps us to choose the system parameters.
Similar to [5], [6] we consider the ensemble of Tanner
graphs G(K; M ; cλ(x); ρ(x)) corresponding to the multipleaccess scheme with K users, M slots, and the degree distributions λ(x) and ρ(x). We are interested in the decoding
performance averaged over the ensemble G(K; M ; λ(x); ρ(x))
in the limit as K,M → ∞.
The major difference of our approach in comparison to [5],
[6] is that we
• consider co-called T -fold IRSA, i.e. collisions of order up
to T can be resolved in slot node with some probability
of error introduced by Gaussian noise;
• take into account a noisy channel (AWGN channel to be
precise);
• take into account finite length effect as the slots have
small length;
• take into account a transmit energy. Assume we use a
strategy with L(x) = x2 . In this case we spent 2 times
more energy while transmitting in comparison to L(x) =
x strategy;
Let us fix the slot length ñ, the number of information bits
k to be sent by each user, the maximal number of iterations
ℓ, the average transmit power P (linear scale) and L(x). Then
the average energy per information bit can be calculated as
follows
ñP L′ (1)
Eb
=
,
N0
2k

User
node

Slot
node

T=4

8
6
4
2
0

0

100

200

300

User count

400

500

600

Fig. 3: Minimum Eb /N0 required to achieve less than 5%
error rate as a user count function

because of finite length effects in the slot. So in what follows
we do not consider infinite number of iterations and fix ℓ.
Proof:
Consider the l-th iteration. Let us consider the slot node
of degree r. We want to calculate the erasure probability of
the outgoing message yl+1 based on incoming messages (with
erasure probabilities xl ). The probability can be calculated as
follows


min(r,T )−1
X
r−1 t
1−
(1 − Pe (ñ, k, P, t))
xl (1 − xl )r−1−t .
t
t=1

Each term in the sum corresponds to a probability of
collision of order t. We are interested only in collisions of
order t ≤ T . The probability of correct outgoing message
decoding is given by 1 − Pe (ñ, k, P, t). We only need to apply
the sum rule of total probability to obtain the needed result.
Recall, that ρr is the probability, that the outgoing edge is
connected to a slot node of degree r.


rX
max
h min(r,T
The rule in user node coincides with the rules from [5], [6].
X)−1
r−1
yl+1 = 1 −
ρr
(1 − Pe (ñ, k, P, t))
t
r=1
t=1
i
IV. N UMERICAL RESULTS
× xtl (1 − xl )r−1−t
We choose the same system parameters as in [1], [3], [4]
xl = λ(yl ), 1 ≤ l < ℓ.
for honest comparison.
xℓ = L(yℓ ).
Parameter
Description
4
n
=
3
×
10
Frame length
Remark 2: We note, that
k = 100
Number of information bits
lim xℓ > 0.
P
=
0.05
Maximum error probability allowed
e
ℓ→∞

K
25
50
100
150
200
250
300
350
400
450
500
550

DE for T = 2, 100 iterations
1.0000x
0.4447x + 0.5553x2
0.1261x + 0.8739x2
0.1155x + 0.8845x2
0.1226x + 0.8774x2
0.1252x + 0.8748x2
0.1591x + 0.6886x2 + 0.1524x3
0.1776x + 0.5895x2 + 0.2329x3
0.1860x + 0.5429x2 + 0.2711x3
0.2005x + 0.4861x2 + 0.3135x3
0.2048x + 0.4620x2 + 0.3333x3
0.2140x + 0.4269x2 + 0.3590x3
0.2218x + 0.3982x2 + 0.3776x3
+0.0015x4 + 0.0005x5
+0.000x6 + 0.0001x7

M
79
61
66
97
128
159
181
205
232
258
286
312

Eb /N0 , dB
1.63
3.09
3.89
4.64
5.46
6.32
7.19
8.03
8.88
9.73
10.60
11.48

339

12.37

K
25
50
100
150
200
250
300
350
400
450
500
550
600

DE for T = 4, 100 iterations
1.0000x
1.0000x
0.6260x + 0.3740x2
0.3190x + 0.6810x2
0.3228x + 0.6772x2
0.3279x + 0.6721x2
0.3259x + 0.6741x2
0.3333x + 0.6667x2
0.3298x + 0.6702x2
0.3349x + 0.6651x2
0.3381x + 0.6619x2
0.3386x + 0.6436x2 + 0.0177x3
0.3445x + 0.6077x2 + 0.0477x3

M
25
41
47
43
57
71
85
99
113
127
140
153
166

Eb /N0 , dB
0.53
1.09
2.84
3.41
4.04
4.75
5.49
6.24
7.03
7.82
8.63
9.46
10.30

K
25
50
100
150
200
250
300
350
400
450
500

DE for T = 1, 100 iterations
0.0920x + 0.9080x2
1.0000x2
1.0000x2
0.0009x + 0.4560x2 + 0.5431x3
0.1138x + 0.0931x2 + 0.7930x3
0.1371x + 0.0146x2 + 0.8482x3
0.1450x + 0.8550x3
0.1466x + 0.8534x3
0.1531x + 0.7928x3 + 0.0540x4
0.1610x + 0.7137x3 + 0.1253x4
0.1647x + 0.6666x3 + 0.1687x4
0.1700x + 0.6125x3
+0.1955x4 + 0.0219x5

M
68
106
195
203
251
309
368
427
482
535
590

Eb /N0 , dB
3.71
4.45
5.79
6.77
7.66
8.54
9.43
10.35
11.28
12.21
13.16

700

15.07

600

600

A. Optimization procedure
The goal is to find the optimal slot count M and a
polynomial L(x) in order to minimize the Eb /N0 under the
maximum error probability allowed.
The optimization procedure is conducted separately for
every user count and consists of two sub-procedures. The first
one is a constrained local minimum search with respect to L
coefficients and the number of slots used in the system. The
constraints are formed by
• Li ≥ 0 ∀i = 1, . . . , Lmax ,
• L(1) = 1
The error probability is minimized under fixed Eb /N0 at this
step. As soon as constrained local minimum search procedures

can search the local minimum only, one need to run multiple
optimization procedures starting from different random initial
points within constraints.
The second sub-procedure is to find a minimum Eb /N0 that
satisfies maximum allowed error probability Pe . We expect the
error probability at the optimal configuration to be a monotonic
function of Eb /N0 and use a binary search.
The numerical experiment results show that L(x) behaves
smoothly when varying the number of users. This means that
a global minimum is found at every optimization point. Note,
that the error probability has multiple local minimums, because
the slot count changes sharply at several points.
B. Simulation results
Interference cancellation algorithm was tested via Gaussian
MAC Monte Carlo simulations. The result of a single run is a
set of slots and the number of simultaneous transmissions (or
collision index) for each slot. Each user selects the number of
transmissions in accordance to L(x) and then selects particular
non-coinciding slots from uniform distribution during each
run. The same Eb /N0 is assumed for all slots.
The decoding is done in accordance to Algorithm 1. The
only thing we need to explain is how we resolve the collisions.
Error probability is set to 1 if the number of simultaneous
transmissions within some slot exceeds the threshold (T ∈
{1, 2, 4}). If the order of collision is less or equal to T ,
then the error probability is calculated independently for each
transmitted message in a slot in accordance to finite length
random coding bound from [1].
R EFERENCES
[1] Y. Polyanskiy, “A perspective on massive random-access,” in Information
Theory (ISIT), 2017 IEEE International Symposium on. IEEE, 2017, pp.
2523–2527.
[2] B. Rimoldi and R. Urbanke, “A rate-splitting approach to the gaussian
multiple-access channel,” IEEE Transactions on Information Theory,
vol. 42, no. 2, pp. 364–375, 1996.
[3] O. Ordentlich and Y. Polyanskiy, “Low complexity schemes for the
random access gaussian channel,” in 2017 IEEE International Symposium
on Information Theory (ISIT), June 2017, pp. 2528–2532.
[4] A. Vem, K. R. Narayanan, J. Cheng, and J.-F. Chamberland, “A userindependent serial interference cancellation based coding scheme for the
unsourced random access gaussian channel,” in Proc. IEEE Information
Theory Workshop (ITW), 2017, pp. 1–5.
[5] G. Liva, “Graph-based analysis and optimization of contention resolution
diversity slotted aloha,” IEEE Transactions on Communications, vol. 59,
no. 2, pp. 477–487, February 2011.
[6] K. R. Narayanan and H. D. Pfister, “Iterative collision resolution for
slotted aloha: An optimal uncoordinated transmission policy,” in 2012
7th International Symposium on Turbo Codes and Iterative Information
Processing (ISTC), Aug 2012, pp. 136–139.
[7] R. Tanner, “A recursive approach to low complexity codes,” IEEE
Transactions on information theory, vol. 27, no. 5, pp. 533–547, 1981.
[8] T. Richardson and R. Urbanke, Modern coding theory.
Cambridge
university press, 2008.

