

\section{Introduction}

Recent years have witnessed a revival of random channel access theory and techniques, fostered by new applications such as grant-free access schemes in \ac{MMA} scenarios \cite{Chen2021:Massive}.
This renewed interest has brought back the problem, known for decades (e.g., \cite{wolf1981:coding,Gallager1985:Perspective}), of framing random access under an information-theoretic setting able to capture not only collisions and intermittent users' activity but also the physical communication process.
Several research efforts have been made into this direction over the years, among which we mention \cite{Mathys1990:Class,Bar-David1993:Forward,Luo2012:New,Chen2017:Capacity,Recep2021:Random}.
Moreover, many recent works in this area have considered an ``unsourced'' model \cite{Polyanskiy2017:Perspective}, in which all users have the same codebook, the receiver is only tasked with producing an unordered list of messages, and the main performance metric is the per-user error probability \cite{Ordentlich2017:low_complexity,Ngo2021:Random_user_activity,vem2019:unsourced,Fengler2021:SPARCs, Liva2021:Coding}.

Coded random access has recently emerged as a new approach to reliably support \ac{MMA} applications, featuring a combination of packet-based coding and \ac{SIC} and having a strong connection with codes on sparse graphs.
Instances of coded random access are \ac{CSA} \cite{paolini2015:csa} and \ac{IRSA} \cite{liva2011:irsa}; in the latter one, packet repetitions are used as a form of packet erasure coding.

Notably, so far the above-mentioned efforts towards a new framework for random access have addressed coded random access only marginally, which motivates us to explore this direction of investigation.
Therefore, in this paper we propose a new approach to \ac{IRSA}, capturing information-theoretic concepts such as codebook construction and information rate.
The specific choice of the users' codebooks, based on \cite{Bar-David1993:Forward}, and the adopted adder channel mode allows incorporating in the analysis some known key quantities, such as the \ac{IRSA} asymptotic load threshold over the \ac{MPR} channel. 
This allows us obtaining achievability and converse results on the average sum rate in the regime in which both the users' population size and the number of slots per frame grow unbounded, their ratio remaining constant.


\section{IRSA over MPR Channel}\label{sec:irsa_mpr}

\subsection{Irregular Repetition Slotted ALOHA}
\ac{IRSA} is a grant-free and uncoordinated access protocol for \ac{MMA}, strongly related to codes on sparse graphs \cite{liva2011:irsa}.
The protocol is grant-free as users perform transmissions with no prior handshake procedure with the receiver. 
It is uncoordinated as users cannot cooperate with each other.
The time is slotted and framed, and users are slot- and frame-synchronous. The number of slots per frame is $N_{\mathrm{s}}$, the total number of users is $K$, the number of simultaneously contending users over the same frame, unknown to the receiver, is $K_{\mathrm{c}} \leq K$.

At the beginning of each frame some users are contending and some others are idle. 
Each non-idle user contends for transmission of one packet over the current frame.
The user samples, independently of the other users, a discrete random variable $D \in \{2,\dots,\bar{d}\}$ with probability distribution $\Pr(D=d) = \Lambda_d$ and \ac{PGF} 
$\Lambda(x) = \sum_{d} \Lambda_d x^d$. 
The distribution $\Lambda$ is the same for all users and is hereafter referred to as the \ac{IRSA} distribution.
The user then draws, uniformly at random and without replacement, $d$ integers between $0$ and $N_{\mathrm{s}}-1$ and transmits $d$ replicas of its packet in the corresponding slots of the frame.
The status of the frame after transmissions can be described by means of a bipartite graph with $K$ user nodes, one per user, and $N_{\mathrm{s}}$ slot nodes, one per slot.
An edge connects user node $u_i$, $i\in\{0,\dots,K-1\}$, to slot node $s_j$, $j\in\{0,\dots,N_{\mathrm{s}}-1\}$, if user $i$ performed transmission of a packet replica in slot $j$.

\begin{example}
An example with $K = 11$ users ($u_0$, $\dots$, $u_{10}$) and $N_{\mathrm{s}} = 13$ slots ($s_0$, $\dots$, $s_{12}$) is depicted in Fig.~\ref{fig:frame}.
Users are represented by circles and slots by squares.
There are $K_{\mathrm{c}} = 7$ contending users, represented by colored circles; the number of transmitted packet replicas may change from user to user.
Blank circles represent users that are idle in the current frame.
\end{example}

\begin{figure}[t]
\centering
         \resizebox{0.50\textwidth}{!}{%
     		\input{./Figures/graph}
     	}%
       \caption{Graphical representation of \ac{IRSA} access with $K=11$ users ($K_{\mathrm{c}}=7$ contending) and $N_{\mathrm{s}}=13$ slots. Light-blue circles are contending users and blank circles idle users. Assuming $T=2$, light-blue squares are resolvable slots, light-red squares collision slots, and blank squares empty slots.}
    \label{fig:frame}
\end{figure}

The efficiency of \ac{IRSA}, denoted by $\eta$, is defined as $\eta = [\Lambda'(1)]^{-1}$ where $\Lambda'(1)$ represents the expected number of replicas transmitted by a contending user.
If users become contending independently of each other with probability $\pi$ at the beginning of each frame, the average load is 
$\mathsf{G} = \pi K/N_{\mathrm{s}}\,\mathrm{[packets/slot]}
$.
The average number of packet replicas per slot is $\mathsf{G} / \eta$.

\subsection{\ac{SIC}-Based \ac{IRSA} Receiver over the \ac{MPR} Channel}

The $T$-\ac{MPR} channel is a packet-based channel model representing a simple extension of the collision channel \cite{Ghez1988:Stability}.
The $T$-\ac{MPR} channel model is based on three assumptions that may be summarized as follows:

\emph{Assumption~1}: The receiver can always discriminate between a slot with no packet arrivals, a slot with at most $T$ arrivals, and a slot with more than $T$ arrivals;
    
\emph{Assumption~2}: If there are more than $T$ arrivals in a slot, a condition detected by the receiver, then none of these packets can be correctly received;
    
\emph{Assumption~3}: If there are at most $T$ arrivals in a slot, a condition detected by the receiver, then all of these packets are correctly received with zero error probability.

Over the $T$-\ac{MPR} channel model, the \ac{IRSA} receiver attempts recovery of all packets using an iterative \ac{SIC}-based procedure.
At the beginning, the receiver marks all slots as empty, resolvable (at most $T$ arrivals), or collision (more than $T$ arrivals) slots.
Then, each iteration comprises two steps and may be described as follows, under the assumption that each replica carries information about the number and the positions of the other replicas:

1. In every resolvable slot, all packets are correctly received.

2. For each such packet, the interference of every replica of the packet is subtracted from the corresponding slot, possibly leading to new resolvable slots.

\begin{example}
With reference again to Fig.~\ref{fig:frame}, assume $T=2$. 
Since slots $s_0$, $s_2$, $s_5$, and $s_7$, are resolvable, packet replicas transmitted by users $u_1$, $u_5$, $u_6$, and $u_{10}$ in these slots are correctly received at the first iteration.
Interference cancellation in the first iteration makes slots $s_4$ and $s_{12}$ resolvable.
In the second iteration, at least one packet replica transmitted by users $u_0$, $u_3$, and $u_8$ is correctly received in these slots.
Interference cancellation in the second iteration makes all slots empty and the procedure terminates successfully.
\end{example}

The \ac{SIC}-based procedure has been analyzed in the asymptotic setting $N_{\mathrm{s}} \rightarrow \infty$, $K \rightarrow \infty$, and $a=K/N_{\mathrm{s}}$ constant \cite{Ghanbarinejad2013:Irregular,stefanovic2018:multipacket}, under the following further assumption:
   
\emph{Assumption~4}: Interference subtraction across slots is ideal.

The analysis resembles density evolution of LDPC codes over the erasure channel and shows the existence of an asymptotic load threshold $\mathsf{G}^{*} = \mathsf{G}^{*}(\Lambda,T)$.
Let $N_{\mathrm{s}} \rightarrow \infty$, $K \rightarrow \infty$, and $a=K/N_{\mathrm{s}}$ be constant. 
In this asymptotic setting, let $p_{\ell}$ be the probability that the generic edge is connected to a slot node not yet resolvable at the end of iteration $\ell$.
Then, the evolution of $p_{\ell}$ through \ac{SIC} iterations is governed by the recursion
\begin{align}
  p_{\ell} &= 1 - \exp\left( - \mathsf{G} \Lambda'(p_{\ell-1}) \right) \sum_{k = 0}^{T - 1} \frac{ 1 }{k!} \left( \mathsf{G} \Lambda'(p_{\ell-1}) \right)^{k}
\end{align}
with starting point $p_1 = 1-\exp(-\frac{\mathsf{G}}{\eta})\sum_{k=0}^{T-1} \frac{1}{k!} (\frac{\mathsf{G}}{\eta})^k$. 
The load threshold is defined as
\begin{align}\label{eq:MPR_threshold}
    \mathsf{G}^{*} = \sup \{ \mathsf{G} > 0 : p_{\ell} \rightarrow 0 \text{ as } \ell \rightarrow \infty\} \, .
\end{align}
\begin{remark}\label{remark:plp}
The quantity $p_{\ell}^d$ represents the probability that the packet of a user, that transmitted $d$ packet replicas, has not yet been correctly received after $\ell$ \ac{SIC} iterations.
Thus the condition $p_{\ell} \rightarrow 0$, which holds for all $\mathsf{G} \leq \mathsf{G}^{*}(\Lambda,T)$, corresponds to a vanishing packet loss probability in the asymptotic setting.
\end{remark}


\section{A New Perspective on \ac{IRSA}} \label{sec:abc}

The description of \ac{IRSA} provided in Section~\ref{sec:irsa_mpr} is the usually adopted one and is typical of collision resolution approaches: it focuses on bursty arrivals and traffic, while it ignores any information-theoretic quantity. 
In this section we formulate a new description in order to fill this gap.
We address the channel model at symbol level, the multiple access code, and the decoding function.
We propose a framework for the $T$-\ac{MPR} channel, including all these aspects, which, on one hand, represents a simple way to realize Assumptions 1-4 above and, on the other hand, provides a connection between random access method and encoding functions and sum rates.

\subsubsection{Channel model} The channel model we employ is the noiseless adder channel \cite{Dyachkov1981:Coding}.
The channel has $K$ inputs $X_1$, $\dots$, $X_{K}$ and one output $Y$, where $X_i \in \{0,1\} \subset \mathbb{R}$ for all $i \in \{1,\dots,K\}$, $Y \in \{0,\dots,K\} \subset \mathbb{R}$, and
\begin{align}
    Y = \sum_{i=1}^{K} X_i
\end{align}
the sum being over the reals.
Due to the binary input alphabets we refer to this channel as the \ac{BAC}.

\subsubsection{Codebook construction and encoding} To define the encoding function of each user we resort on the codebook construction proposed by \ac{BPR} in \cite{Bar-David1993:Forward}, where a coding technique to achieve zero error probability over the ``$K$-choose-$T$'' \ac{BAC} is proposed.
In this channel model there are $K$ users, of which exactly $T$ are contending.
The $T$ binary codewords are transmitted over a \ac{BAC}; the decoder aims at decoding the $T$ messages, with $T$ known a priori, and at associating each message to one of the $K$ users.

The \ac{BPR} construction starts from the parity-check matrix of a $T$-error-correcting binary \ac{BCH} code of length $M=2^m-1$, in the form
\begin{align}\label{eq:H}
    \mathbf{H} = \left[ 
    \begin{array}{ccccc}
        1 & \alpha & \alpha^2 & \dots & \alpha^{2^m-2} \\
        1 & \alpha^3 & \alpha^6 & \dots & \alpha^{3(2^m-2)} \\
        \vdots & \vdots & \vdots & \vdots & \vdots \\
        1 & \alpha^{2T-1} & \alpha^{2(2T-1)} & \dots & \alpha^{(2T-1)(2^m-2)}
    \end{array}
    \right]
\end{align}
with $mT$ binary rows (as the binary image of $\alpha$, a primitive element of $\mathrm{GF}(2^m)$, has length $m$) and $M$ columns.
The columns are partitioned into $K$ disjoint subsets, each of size $\frac{M}{K}$ (assuming $K$ divides $M$) and each subset is employed as the codebook of the corresponding user.\footnote{The assumption that $K$ divides $N_{\mathrm{s}}$ is made throughout the paper. In case $M$ is not a multiple of $K$, one can simply re-define $M$ as the largest multiple of $K$ that is less than $2^m-1$, and assign $M/K$ columns of $\mathbf{H}$ to each user.}
All users have the same information rate and the same codeword length $mT$.
Note that no codeword can be shared by any two users, that all codebooks are nonlinear, and that no codebook contains the all-$0$ codeword.
Note also that, although we stick to \ac{BCH} codes as in \cite{Bar-David1993:Forward}, the codebook construction may in principle rely on other error correcting code families.

The \ac{BPR} construction achieves zero error probability over the $K$-choose-$T$ \ac{BAC}.
In fact, since by construction any $2T$ columns of the parity-check matrix of a $T$-error-correcting linear block code are linearly independent, any two different $T$-tuples of codewords cannot have the same sum.
Hence, the set of $T$ messages can be decoded with no error at the receiver and its message can be uniquely associated with a user.

Next we address the proposed \ac{IRSA} encoder. 
We refer to the described coding scheme as ``\ac{IRSA}-\ac{BPR}''.
\ac{BPR} $(m,T,K)$ codebooks are assigned to the $K$ users, as described above.
At the beginning of a frame, each user has an idle message $W=0$ (meaning nothing to communicate) with probability $1-\pi$ and one message of information $W \in \{1,\dots,\frac{M}{K}\}$ with probability $\pi$, independently from user to user. 
Users with a message $W \neq 0$ are contending ones and the message of each contending user is uniformly distributed in $\{1,\dots,\frac{M}{K}\}$.
An idle user generates an idle sequence $X^N(0)$ of $N = (1+mT) N_{\mathrm{s}}$ symbols, all equal to $0 \in \mathbb{R}$.
On the other hand, a contending user generates a binary codeword $X^N(W)$ of length $N$ symbols, in the following way.
The message $W$ is encoded into a codeword of length $mT$ belonging to the user's \ac{BPR} codebook and one extra-symbol equal to $1 \in \mathbb{R}$ is appended to the \ac{BPR} codeword.
Then, the length-$N$ codeword is constructed as the concatenation of $d$ ``\ac{BPR} blocks'', each containing the \ac{BPR} codeword with the extra symbol $1$, and of $N_{\mathrm{s}}-d$ ``idle blocks'', each of length $1+mT$ and containing the symbol $0 \in \mathbb{R}$ only.
Importantly, to reflect the grant-free and uncoordinated nature of the access scheme, the number of \ac{BPR} blocks in the codeword, $d$, and the positions of these $d$ blocks are functions solely of the random message $W$.
A way to generate the repetition degree $d$ and the positions of the $d$ \ac{BPR} blocks out of $W$ is discussed in the Appendix.

\begin{remark}
Each of the $N_{\mathrm{s}}$ blocks composing a codeword $X^N(W)$ corresponds to one slot in the description provided in Section~\ref{sec:irsa_mpr}.
As such, the codeword of a contending user corresponds to the entire frame.
This is consistent with the message $W$ being transmitted using the channel $N$ times.
The information rate of a contending user is $R=r/N_{\mathrm{s}}$ where
\begin{align}\label{eq:rate_bpr}
    r = \frac{1}{1+ m T} \log_2 \frac{M}{K}
\end{align}
is the \ac{BPR} encoder rate with the extra symbol $1$.
The average sum rate, $R_{\mathrm{sum}}$, is given by $R_{\mathrm{sum}} = \mathbb{E}[K_{\mathrm{c}}]\, R$.
We note also that the encoder may be seen as the concatenation of two component encoders: a nonlinear \ac{BPR} encoder and an \ac{IRSA} ``random access'' encoder.
\end{remark}

\begin{remark}
The IRSA-BPR construction provides different codebooks to different users, thus allowing the receiver to identify the users that are sending messages. 
A slightly simplified IRSA coding scheme may be also defined for the unsourced setting, where each user can use the entire codebook without any prior assignment, and the receiver is only able to produce an unordered list of messages.  The information rate for this unsourced construction can be easily derived, leading to an encoder rate expression as in (1), but without the term $\log_2K$, which appears as the cost of identifying the users that send messages. However, we should note that in the unsourced model the function of message association to users is left to upper layer protocols that spend at least $\log_2K$ bits  in the overhead of each message to accomplish this task.
\end{remark}

\subsubsection{Iterative Decoding} The vector $Y^N$ at the output of the \ac{BAC} is a sequence of $N_{\mathrm{s}}$ blocks, each of length $1+mT$ symbols.
We say a contending user is active in any such block when a \ac{BPR} block is present in that position in the user's codeword.
Decoding is performed iteratively; in every iteration all non-zero blocks of $Y^N$ are processed and, for each of them, \ac{BPR} decoding is run if the number of active users, known owing to the extra-symbol $1$, does not exceed $T$.
Each message $W$ decoded from a block can be associated with no error to a specific user; $W$ is re-encoded and the obtained length-$N$ codeword is subtracted from $Y^N$.
No action is taken in a block if the number of active users in it exceeds $T$.
Decoding terminates when $Y^N = 0^N$ (success) or when $Y^N \neq 0^N$ but no further subtraction can be performed (premature stop).

Denoting the iterative decoding function by $\phi(\cdot)$, we have 
\begin{align}
\phi(Y^N) = \{ (W_{1},\dots,W_{q}), (i_1,\dots,i_q), \mathsf{F} \}
\end{align}
where $(W_1,\dots,W_q)$ is an ordered message list, $(i_1,\dots,i_q)$ is the ordered list of the corresponding user's indexes, $\mathsf{F}=0$ flags a success ($q=K_{\mathrm{c}}$, complete message list), and $\mathsf{F}=1$ flags a premature stop ($q<K_{\mathrm{c}}$, incomplete message list).

For any random access coding scheme we distinguish between the decoding error probability (probability that the obtained message list is different from the actual one and/or some incorrect user-message association is done) and the per-user error probability (probability that the message of a user is not in the decoded message list and/or that the user is not associated with its message).


\section{Results}\label{sec:results}

We provide both achievability and converse results on the expected sum rate.
The achievability one applies to the \ac{IRSA}-\ac{BPR} scheme, while the converse has a more general validity.
We always assume that, in each frame, each user is contending with probability $\pi$, independently of the other users.

\begin{theorem}\label{th:achievability}
Consider an \ac{IRSA}-\ac{BPR} scheme over the \ac{BAC}, with distribution $\Lambda$ and parameters $T$ and $m = \frac{1}{\epsilon} \log_2 K$, $0<\epsilon<1$.
If 
\begin{align}\label{eq:achievability} 
  R_{\mathrm{sum}} \leq \frac{1-\epsilon}{T} \, \mathsf{G}^{*}(\Lambda,T)
\end{align}
then the per user error probability under iterative decoding tends to zero in the limit as $N_{\mathrm{s}} \rightarrow \infty$ and constant $a=K/N_{\mathrm{s}}$, where $\mathsf{G}^{*}(\Lambda,T)$ is the load threshold of the \ac{IRSA} distribution $\Lambda$ over the $T$-\ac{MPR} channel model, defined in \eqref{eq:MPR_threshold}.
\end{theorem}
\begin{IEEEproof}
In the considered setting, Assumptions 1-4 reviewed in Section~\ref{sec:irsa_mpr} are all satisfied.
In fact, due to the addition of the extra symbol to each \ac{BPR} codeword, the receiver has constantly perfect knowledge of the number of \ac{BPR} blocks in each slot (Assumption~1) and takes no action in any slot with more than $T$ such blocks (Assumption~2).
Moreover, up to $T$ \ac{BPR} blocks in the same slot can always be decoded with zero error probability (Assumption~3).
Finally, over the \ac{BAC} interference subtraction is perfect since the channel is noiseless and no channel estimation is required. As such, iterative decoding for \ac{IRSA}-\ac{BPR} over the \ac{BAC} has a one-to-one correspondence with \ac{SIC} over the \ac{MPR} channel (Section~\ref{sec:irsa_mpr}) and the per-user error probability coincides with the packet loss probability mentioned in Remark~\ref{remark:plp}.
Next, the average sum rate is
\begingroup
\allowdisplaybreaks
\begin{align}
    R_{\mathrm{sum}} &= \mathbb{E}[K_{\mathrm{c}}] \frac{r}{N_{\mathrm{s}}} = \frac{\mathsf{G}}{1+ \frac{T}{\epsilon} \log_2 K} \log_2 \frac{K^{\frac{1}{\epsilon}} -1}{K} \label{eq:rsum_exact}
\end{align}
\endgroup
where \eqref{eq:rsum_exact} follows from \eqref{eq:rate_bpr} and $m = \frac{1}{\epsilon} \log_2 K$.
As $N_{\mathrm{s}} \rightarrow \infty$ for constant $a$, the per-user error probability vanishes for all $\mathsf{G} \leq \mathsf{G}^{*}(\Lambda,T)$ under \ac{SIC} decoding. 
Since
\begin{align}\label{eq:limit_K_eps}
\frac{\log_2 \frac{K^{\frac{1}{\epsilon}} -1}{K} }{1+ \frac{T}{\epsilon} \log_2 K} \rightarrow \frac{1-\epsilon}{T}   
\end{align}
as $K = a N_{\mathrm{s}} \rightarrow \infty$, we obtain the statement.
\end{IEEEproof}

\begin{remark}
We note that the slot size (number of channel uses per slot), and then the ``packet'' size, is $\Theta(\log_2 K)$.
We may interpret this as a consequence of the decoder task to perform association between decoded messages and contending users.
\end{remark}

We now address a converse result. We start by proving the following useful lemma.

\begin{lemma}\label{lemma:loeve}
Let $C$ be any positive random variable.
For constant $a = K/N_{\mathrm{s}}$, if 
$
\lim_{\substack{N_{\mathrm{s}} \rightarrow \infty}} \Pr(K_{\mathrm{c}} > C) = 0
$
then
\begin{align}\label{eq:G_ineq_conv}
    \mathsf{G} \leq \lim_{N_{\mathrm{s}} \rightarrow \infty} \frac{\mathbb{E}[C]}{N_{\mathrm{s}}} \, .
\end{align}
\end{lemma}
\begin{IEEEproof}
The statement can be proved by applying the simple lower bound on the probability of the upper tail provided in Lo{\'e}ve \cite{loeve1977:Probability}, stating that for a real random variable $X$ with support $\mathcal{X}$ and a nonnegative and nondecreasing function $g(\cdot) : \mathbb{R} \mapsto \mathbb{R}$ we have
\begin{align}\label{eq:loeve}
    \Pr(X > a) \geq \frac{\mathbb{E}[g(X)]-g(a)}{\sup g(x)}
\end{align}
where $\sup g(x) = \sup \{g(x) : x \in \mathcal{X} \}$.
Applying \eqref{eq:loeve} with $X = K_{\mathrm{c}} - C$, $g(x)=\max\{0,x\}$, and $a=0$, we obtain
\begingroup
\allowdisplaybreaks
\begin{align}
\Pr(K_{\mathrm{c}} > C) &\geq \frac{\mathbb{E}[\max\{0,K_{\mathrm{c}}-C\}]}{\sup g(k_{\mathrm{c}}-c)} \\
&\geq \frac{\max\{0,\mathbb{E}[K_{\mathrm{c}}]-\mathbb{E}[C]\}}{\sup g(k_{\mathrm{c}}-c)} \label{eq:jensen}
\end{align}
\endgroup
where \eqref{eq:jensen} follows from Jensen's inequality since $g(x)$ is convex.
By hypothesis, for any $\epsilon>0$ there exists $N_{\mathrm{s}}(\epsilon)$ such that $\Pr(K_{\mathrm{c}} > C) \leq \epsilon$ for all $N_{\mathrm{s}} > N_{\mathrm{s}}(\epsilon)$.
It follows that, for all $N_{\mathrm{s}} > N_{\mathrm{s}}(\epsilon)$, we also have
\begin{align}
\frac{\max\{0,\mathbb{E}[K_{\mathrm{c}}]-\mathbb{E}[C]\}}{\sup g(k_{\mathrm{c}}-c)} \leq \epsilon
\end{align}
and then
\begingroup
\allowdisplaybreaks
\begin{align}
\max\{0,\mathbb{E}[K_{\mathrm{c}}]-\mathbb{E}[C]\} &\leq \epsilon \, \sup g(k_{\mathrm{c}}-c) \\
&\leq \epsilon\, K \label{eq:eps_K}
\end{align}
\endgroup
where \eqref{eq:eps_K} is due to $k_{\mathrm{c}} \leq K$ and $c > 0$. Inequality \eqref{eq:eps_K} implies
$\pi K -\mathbb{E}[C] \leq \epsilon \, K$. Dividing both sides by $N_{\mathrm{s}}$ we obtain
$\mathsf{G} \leq \frac{\mathbb{E}[C]}{N_{\mathrm{s}}} + \epsilon \, a$.
Taking the limit $N_{\mathrm{s}} \rightarrow \infty$, $\epsilon$ becomes arbitrarily small; noting that $a$ is constant (so $\epsilon \, a$ vanishes) yields the statement.
\end{IEEEproof}

\medskip
We can use Lemma~\ref{lemma:loeve} to obtain a converse result valid for any framed and slotted access scheme over the \ac{BAC} (even cooperative or grant-based) with \ac{BPR} codebooks assigned to users and the slot size matching the \ac{BPR} codeword size.
We keep appending the extra symbol $1$ to the \ac{BPR} codeword, although not strictly necessary for the proof.

\begin{theorem}\label{th:converse}
Let \ac{BPR} codebooks be assigned to the $K$ users, with $m = \frac{1}{\epsilon} \log_2 K$, and the channel model be the \ac{BAC}.
Assume each contending user generates one \ac{BPR} codeword of length $n=1+mT$ out of its message and transmits replicas of it in any number of slots, where the slot size is also $n$, according to any access protocol.
Length-$n$ all-zero words are transmitted by the user in the other slots.
Moreover, let $l_i$ be the number of \ac{BPR} codewords added in slot $i$ and 
\begin{align}\label{eq:ci}
C_i = \left\{ 
\begin{array}{ll}
   l_i  & \text{if } l_i \leq T \\
   T  & \text{if } l_i > T .
\end{array}
\right.
\end{align}
Let $P_e$ be the error probability under optimum decoding.
If $P_e \rightarrow 0$ as $N_{\mathrm{s}} \rightarrow \infty$ for constant $a = K / N_{\mathrm{s}}$, then
\begin{align}\label{eq:converse}
R_{\mathrm{sum}} \leq \frac{1-\epsilon}{T} \, \mathbb{G}
\end{align}
where $\mathbb{G}$ is the sup of the set of all $\mathsf{G}$ fulfilling \eqref{eq:G_ineq_conv} and $C = \sum_{i=0}^{N_{\mathrm{s}}-1} C_i$ with $C_i$ defined in \eqref{eq:ci}.
\end{theorem}
\begin{IEEEproof}
An optimum, idealized decoder is the one aware of which users are active in each slot and formulating the decoding problem over the \ac{BAC} as the solution of a linear system of equations in which the unknowns are the $K_{\mathrm{c}}$ \ac{BPR} codewords.
The number of linearly independent equations available in slot $i$ is $C_i$ defined in \eqref{eq:ci}, so the total number of such equations is $C = \sum_{i=0}^{N_{\mathrm{s}}-1} C_i$.
If the error probability of this optimum decoder vanishes as $N_{\mathrm{s}} \rightarrow \infty$ and constant $a = K/N_{\mathrm{s}}$, then the probability that the number of unknown exceeds the number of equations, $\Pr(K_{\mathrm{c}} > C)$, also vanishes.
Lemma~\ref{lemma:loeve}, with \eqref{eq:rsum_exact} and \eqref{eq:limit_K_eps}, then leads to the statement. 
\end{IEEEproof}

\begin{remark}
Comparing \eqref{eq:achievability} and \eqref{eq:converse}, we can note how their structure is analogous.
As mentioned above, however, while Theorem~\ref{th:achievability} applies to \ac{IRSA}-\ac{BPR} under \ac{SIC} decoding, Theorem~\ref{th:converse} has a broader scope. 
A more subtle difference is that Theorem~\ref{th:achievability} considers the per-user error probability under iterative decoding while Theorem~\ref{th:converse} the decoding error probability under an optimum decoder.
\end{remark}

\begin{example}
Consider the following three slotted and framed access schemes: (i) A coordinated scheme where each contending user fills one slot with a \ac{BPR} block and the other slots with all-zero blocks; the slot index is scheduled by the receiver to maximize the sum rate. (ii) An uncoordinated scheme where all contending users employ \ac{IRSA}-\ac{BPR}. (iii) A mixed scheme in which $\nu K$ users have high priority and are served in a coordinated fashion, as in scheme (i), while the other $(1-\nu) K$ users employ \ac{IRSA}-\ac{BPR}; $\gamma N_{\mathrm{s}}$ slots are reserved to high-priority users while the other $(1-\gamma) N_{\mathrm{s}}$ slots are available to low-priority ones, but the high-priority slots still empty after scheduled transmissions can be used by low-priority users as per decoder feedback.
Specifying \eqref{eq:G_ineq_conv} for the three schemes, we obtain $\lim_{N_{\mathrm{s}} \rightarrow \infty} \mathbb{E}[C]/N_{\mathrm{s}} = \min \{\mathsf{G},T\}$, hence $\mathbb{G}=T$, for scheme (i). Proof sketch: $K_{\mathrm{c}}/N_{\mathrm{s}} \rightarrow \mathsf{G}$ in probability as $N_{\mathrm{s}} \rightarrow \infty$; $f(x)=\min\{x,T\}$ is continuous so $C/N_{\mathrm{s}}=f(K_{\mathrm{c}}/N_{\mathrm{s}}) \rightarrow f(\mathsf{G})$ in probability; $C/N_{\mathrm{s}}$ is bounded then we can conclude that $\mathbb{E}[C/N_{\mathrm{s}}] \rightarrow f(\mathsf{G})$. For scheme (iii) we obtain (proof omitted)
\begin{align*}
    \mathsf{G} &\leq T - (1 - \beta)
    \exp\! \bigg(\!\! - \frac{\mathsf{G} (1-\nu)}{\eta (1-\beta)} \bigg) \!\sum_{t=0}^{T-1} \frac{T-t}{t!} \bigg( \frac{\mathsf{G} (1-\nu)}{\eta (1 - \beta)} \bigg)^{\!t}
\end{align*}
where $\beta = \min \{ \frac{\nu \mathsf{G}}{T}, \gamma \}$; this expression holds also for scheme (ii) with $\nu=\beta=0$. In both schemes (ii) and (iii), $\mathbb{G}$ must be computed numerically.
The obtained values of \eqref{eq:converse} are plotted in Fig.~\ref{fig:converse} versus $T$ for $\epsilon=0.99$.
Two values of $\eta$ are considered, namely, $\eta=1/2$ and $\eta=1/3$; concerning the mixed scheme, the plot is for $\nu=\gamma=0.2$.
The region above each curve is not achievable by the corresponding scheme.
The value of $\mathbb{G}$ for scheme (ii) also appears in \cite{stefanovic2018:multipacket}, but it was proved only under \ac{SIC}, while it is shown here that it holds for any decoder.
\end{example}

\begin{figure}
    \begin{center}
    \includegraphics[width=0.98\columnwidth]{./Figures/Figure2.pdf}
    \end{center}
    \vspace{-5mm}
    \caption{Converse \eqref{eq:converse} versus $T$ for $\epsilon=0.99$. Solid: coordinated scheme; dashed: \ac{BPR}-\ac{IRSA} scheme; dot-dashed: mixed scheme. \ac{IRSA} efficiency $\eta=1/2$ ($\mathsf{o}$) and $\eta=1/3$ ($\mathsf{x}$).}
    \label{fig:converse}
\end{figure}

\begin{comment}
\begin{figure}[t]
        \begin{center}
        \resizebox{0.5\textwidth}{!}{%
    		\input{ISIT_2022/Figures/converse}
    	}%
    	\end{center}
    \caption{Converse \eqref{eq:converse} versus $T$ for $\epsilon=0.99$. Solid: coordinated scheme; dashed: \ac{BPR}-\ac{IRSA} scheme; dot-dashed: mixed scheme. \ac{IRSA} efficiency $\eta=1/2$ ($\mathsf{o}$) and $\eta=1/3$ ($\mathsf{x}$).}
    \label{fig:converse}
\end{figure}
\end{comment}


\section{Conclusion}\label{sec:conclusions}

In this paper a new framework for \ac{IRSA} has been proposed, in which rigorous results on the average sum rate can be established.
A number of possible research directions, we believe, arise from this work. 
Among them, the development of converse results capturing the \ac{IRSA} distribution (and not just its efficiency), extension to \ac{CSA} schemes, extensions to channel models incorporating noise and fading and to different settings, e.g., to asynchronous schemes or to a finite number of users generating an increasing traffic as the frame size grows.


\section*{Appendix}
This appendix discusses generation of the repetition rate $d$ and of a $d$-tuple of different integers in $\{0,\dots,N_{\mathrm{s}}-1\}$ as a function of a message $W$ uniformly distributed in $\{1,\dots,\frac{M}{K}\}$.
For $\frac{M}{K} \Lambda_d$ an integer for all $d\in\{2,\dots,\bar{d}\}$, an instance of the random variable $D$ with \ac{PGF} $\Lambda(x)$, mentioned in Section~\ref{sec:irsa_mpr}, can be generated as
\begin{align}\label{eq:d_from_W}
    d = \min \bigg\{ i \in \{2,\dots,\bar{d}\} : \frac{M}{K} \sum_{h=2}^{i} \Lambda_h \geq W \bigg\} \, .
\end{align}
Once the repetition degree $d$ has been obtained from \eqref{eq:d_from_W}, the positions of the $d$ \ac{BPR} blocks can be generated by resorting on the combinadic representation of an integer (e.g., \cite{Knuth2011:Art}).
Accordingly, for any integer $0 \leq u < \binom{N_{\mathrm{s}}}{d}$, there exists a unique $d$-tuple of integers $(u_1,\dots,u_d)$, with $0 \leq u_1 < \dots < u_{d}$, such that 
$u = \binom{u_1}{1} + \binom{u_2}{2} + \dots + \binom{u_d}{d}$. %
In particular, for $h = d, \dots, 1$, $u_h$ is computed as
\begin{align}\label{eq:u_h}
    u_h = \max \bigg\{ i \in \mathbb{N} : \binom{i}{h} \leq u - \sum_{j=h+1}^{d} \binom{u_j}{j} \bigg\} \, .
\end{align}
The positions of the $d$ blocks can be computed by first letting $v = W-\frac{M}{K}\sum_{i=2}^{d-1} \Lambda_i-1$ (note that $v \in \{0,\dots,\frac{M}{K}\Lambda_d-1\}$), then by defining $u = v \mod \binom{N_{\mathrm{s}}}{d}$, and finally by returning $(u_1, \dots, u_d)$ through \eqref{eq:u_h}.
The desired uniform probability distribution over the $\binom{N_{\mathrm{s}}}{d}$ combinations is obtained when $\binom{N_{\mathrm{s}}}{d}$ divides $\frac{M}{K} \Lambda_d$ for all $d\in\{2,\dots,\bar{d}\}$.

\section*{Acknowledgement}
This work has been carried out in the framework of the CNIT National Laboratory WiLab and the WiLab-Huawei Joint Innovation Center.
The authors would like to thank Dr. Lei Wang for useful discussions.



