Finite-Blocklength Results for the A-channel Applications to Unsourced Random Access and Group Testing

2025-04-27 0 0 484.86KB 11 页 10玖币

侵权投诉

Finite-Blocklength Results for the A-channel:

Applications to Unsourced Random Access and

Group Testing

Alejandro Lancho, Alexander Fengler and Yury Polyanskiy

Abstract—We present ﬁnite-blocklength achievability bounds

for the unsourced A-channel. In this multiple-access channel,

users noiselessly transmit codewords picked from a common

codebook with entries generated from a q-ary alphabet. At each

channel use, the receiver observes the set of different transmitted

symbols but not their multiplicity. We show that the A-channel

ﬁnds applications in unsourced random-access (URA) and group

testing. Leveraging the insights provided by the ﬁnite-blocklength

bounds and the connection between URA and non-adaptive group

testing through the A-channel, we propose improved decoding

methods for state-of-the-art A-channel codes and we showcase

how A-channel codes provide a new class of structured group

testing matrices. The developed bounds allow to evaluate the

achievable error probabilities of group testing matrices based on

random A-channel codes for arbitrary numbers of tests, items

and defectives. We show that such a construction asymptotically

achieves the optimal number of tests. In addition, every efﬁciently

decodable A-channel code can be used to construct a group

testing matrix with sub-linear recovery time.

I. INTRODUCTION

We consider the problem where Kusers transmit symbols

from a q-ary input alphabet [q] = {1, . . . , q}over a noiseless

channel. Speciﬁcally, let ci,j ∈[q]be the transmitted symbol

from user j∈[K]at channel use i. The channel output Yiat

channel use iis given by

Yi=

[

j=1

ci,j .(1)

In this channel, sometimes referred to as A-channel [1], [2],

the receiver observes the set of transmitted symbols but not

who transmitted them, and also not the multiplicity.1The A-

channel was introduced by Chang and Wolf in [1] as the

“T-user M-frequency channel without intensity information”,

and it is also known as the hyperchannel [3]. The mutual

information of the A-channel under uniform inputs was ob-

tained in [1]. Its limit when Kand qtend to inﬁnity but

The authors are with the Department of Electrical Engineering and Com-

puter Science, Massachusetts Institute of Technology, Cambridge 02139,

MA, USA (e-mails: {lancho,fengler,yp}@mit.edu). Alejandro Lancho has

received funding from the European Union’s Horizon 2020 research and

innovation programme under the Marie Sklodowska-Curie grant agreement

No. 101024432. Alexander Fengler was funded by the Deutsche Forschungs-

gemeinschaft (DFG, German Research Foundation) – Grant 471512611. This

work is also supported by the National Science Foundation under Grant No

CCF-2131115.

1Note that, for the case where K= 2, the multiplicity can be inferred from

the cardinality of Y, and thus, for q= 2, the A-channel is equivalent to the

binary-adder channel (BAC).

its ratio λ=K/q is ﬁxed was studied in [2]. Speciﬁcally,

in [2], it was shown that in this limit the mutual information

grows proportional to q. Also in [2], it was shown that

uniform inputs are not optimal in general, although they

become optimal in the limit λ→0and when λ= ln 2,

where ln(·)denotes the natural logarithm. Besides, when the

input distributions of the users are constrained to be equal,

uniform distributions become asymptotically optimal for all

λ≤ln 2 [2]. The mutual information with uniform inputs

in the sparse limit of K, q → ∞ with ﬁxed ratio (log K)/q

was computed in [4] and it was shown that in this limit the

mutual information grows proportional to log q. Furthermore,

in this regime the simpliﬁed cover decoder, which checks each

codeword individually for consistency with the channel output,

is optimal. For general Kand q, the optimal input distribution

as well as the capacity of the A-channel are still unknown.

In the case where all users transmit their messages from a

common codebook, we will refer to (1) as the unsourced A-

channel. Under this setup, the receiver can only recover a list

of transmitted codewords up to permutation. The information

theoretic question of multiple-access in the unsourced setting

was ﬁrst formulated in [5] for the AWGN multiple-access

channel (MAC), where it was established that a relevant setup

should consider the following aspects: i) the decoder only aims

to return a list of messages without recovering users’ identities;

ii) the error event should be deﬁned per user; iii) the error

probability has to be averaged over the users; iv) each user

sends a ﬁxed amount of information bits within a ﬁnite frame

length.

This formulation is well suited for short-packet random-

access wireless communications since, in theory, it does

not require coordination among users. As such, it captures

the requirements of massive machine-type communications

(mMTC), one of the new emerging communication scenarios

in next generation wireless networks, where a huge amount

of battery-limited devices is expected to connect sporadically

to the network to send short information packets. Since its

inception, this problem has been commonly referred in the

literature as unsourced random access (URA). Several papers

establishing fundamental limits for different relevant multiple-

access channel models and setups appeared since then (see,

e.g., [6]–[9]), and many transmission schemes trying to per-

form as close as possible to this fundamental limits has been

proposed (e.g., [10]–[12]).

arXiv:2210.01951v1 [cs.IT] 4 Oct 2022

The A-channel played an important role for codes design in

URA. In [13], a coding scheme for AWGN URA termed coded

compressed sensing (CCS) was introduced. It used a random

inner code of size qconcatenated with an outer q-ary A-

channel code. The A-channel code constructed for this purpose

was termed tree code. The ﬂexibility of this code construction

allowed it to be extended to different channel models. Several

follow-up works on URA (e.g, [11], [14]–[17]) made use of

an outer A-channel code. In [4] an asymptotically Bayesian

optimal inner decoder for the AWGN channel was constructed

and it was shown that the CCS construction can achieve the

Shannon limit when Kand qgrow but its ratio λ→0.

However, in practical applications the density λis not zero.

The A-channel is of relevance to URA in a more general

sense: Every unsourced K-user code for Bbits at blocklength

n0can be extended to a code of length nn0for nBRA(n, K)

bits by concatenating with an outer unsourced A-channel

code of rate RAwith nA-channel uses. The loss in rate of

RAdoes not appear in classical multiple-access where user

identiﬁcation is done based on the codebook. A system that

can transmit 1 bit for each user with zero error can be used

to transmit arbitrary many bits by simple repetition. For the

unsourced channel this is not possible and an outer A-channel

code is necessary to couple repeated transmissions.

Furthermore, the blocklength of the outer A-channel used

for concatenated coding (e.g., [4], [13], [14]) is in the order of

10 −40. Therefore, the asymptotic results for the A-channel

are not necessarily insightful for code design.

In this paper, we study the unsourced A-channel in the ﬁnite

blocklength regime with arbitrary Kand q. In particular, we

present two novel non-asymptotic achievability bounds. Also,

we provide a second-order asymptotic approximation whose

relevance is validated by means of numerical examples in

different scenarios of interest.

The A-channel ﬁnds interesting applications in noiseless

non-adaptive group testing. The goal in group testing is to

identify Kdefective items in a large population of Nitems

by applying Tbinary tests. A group-testing design is a

T×Nbinary matrix where each column speciﬁes the test

in which that item participates. A test is declared positive

if at least one tested item is defective. Group testing was

developed by Dorfman in 1943 [18] for syphilis testing.

Dorfman discovered that it is possible to test more people

with a limited number of tests by pooling blood samples

together. The topic has seen a recent rise in popularity since

the COVID-19 pandemic led to a shortage of available tests for

which group testing provides an appropriate solution. Group

testing ﬁnds further important applications in DNA screening,

large scale manufacturing control, neighborhood discovery,

random access, machine learning, anomaly detection in routing

networks, etc. [19]–[23]. For a recent survey on group testing

from an information theoretic view, see [24].

The connection to the A-channel is as follows: Each code-

book for the unsourced q-ary A-channel with blocklength n

and size Mgives rise to a group-testing design for N=M

items with T=nq tests. To convert the codebook to a group-

testing design, each q-ary symbol ciis converted to a binary

vector of size qwith a 1 at position ci. The defective items

take the role of the transmitting users and the set of defective

items can be obtained by recovering the transmitted messages.

This A-channel group-testing design has a ﬁxed number nof

tests per item. The pair (n, q)can be used to optimize the

group-testing design.

It is known that a ﬁxed number of tests leads to improved

error probabilities compared to an independent and identically

distributed (i.i.d.) Bernoulli test design, even if the average

number of tests is the same [24]. A popular design, analyzed in

[25], uses a ﬁxed number of tests per item, which are chosen at

random from all tests. Compared to that, an A-channel design

offers more structure as each item participates in exactly one of

each group of qtests. The Kautz-Singleton (KS) construction

[26] is another popular group-testing design that naturally

has a q-ary structure. In particular, it is based on a q-ary

Reed-Solomon code of length n. The KS construction was

recently shown to be optimal for probabilistic group testing

in certain scaling regimes [27]. The random coding bound

developed in this paper gives a concrete ﬁnite blocklength

achievability result for a random, but highly structured, group-

testing design.

Motivated by the insights of our results and the algorithms

developed in group testing, we also propose an improved

decoder for the tree code. Numerical simulations conﬁrm that

the improved decoder signiﬁcantly increases the achievable

rates of the tree code.

II. FINITE-BLOCKLENGTH FRAMEWORK

We consider the channel model introduced in (1), where

Kusers transmit codewords from a common codebook with

entries drawn from a q-ary input alphabet [q] = {1, . . . , q}

over nchannel uses of a noiseless channel. To denote the

n-length input-output relation, we shall also write

Y=[

j∈[K]

cj(2)

where cj∈[q]ndenotes the codeword transmitted by user j.

We next deﬁne the notion of URA code for the A-channel.

Deﬁnition 1 (Code): Let [a]

bdenote the set of combina-

tions of b-element subsets of [a]. Assume q > K, and let

Wj,j∈[K], denote the transmitted message by user j.

An (M, n, )-code for the unsourced A-channel (2), where

cj∈[q]n, consists of an encoder-decoder pair,

•encoder: f: [M]7→ [q]n;

•decoder: g:nSK

k=1 [q]

kon7→ [M]

K,

satisfying either the per-user probability of error (PUPE)

P(p)

e,P[{Wj/∈g(Y)}∪{Wj=Wi, j 6=i}]≤(3)

or the joint probability of error (JPE)

P(j)

e,P{{Wj}K

j=1 6=g(Y)}∪{Wj=Wi, j 6=i}≤.

(4)

We assume that {Wj}K

j=1 are independent and uniformly

distributed on [M], and that f(Wj) = cj∈[q]n. For each

type of error probability, we say the code achieves a rate

R= log2M/n.

Hence, we have Kusers selecting randomly a codeword

from a common codebook, and the decoder’s task is to provide

an estimate of the transmitted list of length K. In this paper,

we assume Kis known at the receiver.

A. Achievability Non-Asymptotic Bounds

In this section, we present our ﬁnite-blocklength achievabil-

ity bounds for the unsourced A-channel. To do so, we consider

a random-coding scheme where a codebook Ccontains Mran-

domly generated codewords of length ndistributed according

to PX(c) = Qn

i=1 PX(ci), where PX= Unif[q]. According

to Deﬁnition 1, user jselects uniformly at random a message

Wj∈[M], and transmits the corresponding encoded codeword

f(Wj) = cj. Due to symmetry, we assume without loss of

generality that the ﬁrst Kcodewords are transmitted. We shall

consider two different decoders, which will lead to our two

different achievability bounds:

Cover decoder:From the received sequence Y, the

decoder ﬁrst discards all codewords from the codebook that

are incompatible with the received sequence, i.e., those ones

that are not covered by Y. Then, the decoder outputs a

list of Kcodewords chosen uniformly at random from the

surviving codewords. Since the A-channel is noiseless, the

list of surviving codewords always contains the transmitted

list plus Nfa,c∈[0 : M−K]false alarms. Therefore, P(p)

can be upper-bounded by the PUPE achieved by this decoding

rule, namely, P(p)

e≤ENfa,c hNfa,c

K+Nfa,c i. Similarly, P(j)

ecan be

upper-bounded by the probability of having at least one false

alarm, i.e., P(j)

e≤P[Nfa,c ≥1].

Joint decoder:This decoder ﬁnds all combinations of K

codewords from the codebook that can be selected to generate

the output Y. If there is more than one valid combination, the

decoder chooses one, uniformly at random, and outputs the

list of indices in that combination. Note, that this is exactly

the maximum likelihood decoder. Since the A-channel is

noiseless, the combination containing only the Ktransmitted

codewords will always be valid. A wrong combination will

differ from the correct one in Nfa,j =Nmd,j indices, i.e.,

same number of misdetections and false alarms. Hence, we

can bound the error probability as P(p)

e≤ENfa,j hNfa,j

Kiand

P(j)

e≤P[Nfa,j ≥1].

Remark 1: Recall that, in this paper, we assumed Kto be

known at the receiver. The cover decoder does not require this

knowledge and works unaltered if Kis unknown. The joint

decoder can be adopted in two ways to deal with the missing

information. One possibility is to extend the code design and

use additional channel uses to estimate the number of users.

Another way is to let the receiver ﬁnd the smallest set of

messages that recreate the channel output, as in the smallest

satisfying set algorithm in group testing [24].

We are now ready to present our two achievability bounds.

Theorem 1 (Cover decoding): There exists an (M, n, )-code

for the unsourced K-user A-channel with PUPE satisfying

≤

K−1

`=1

K+`E"min(1,M−K

`K

k=1k

qAk`)#

+E"min(1,M−K

KK

k=1k

qAkK)#+K

2

M(5)

and there exists an (M, n, )-code with JPE satisfying

≤K

2

M+E"min(1,(M−K)

k=1k

qAk)#.(6)

In both (5) and (6), Akis the k-th element of A=

[A1, . . . , AK]T, which is a multinomial-distributed random

vector with ntrials and Kpossible outcomes with probabilities

{pk}K

k=1, which are given by

pk=q!S(K, k)

(q−k)!qK(7)

where S(K, k)denotes the Stirling number of the second kind

[28, Sec. 26.8.6].

Proof: See Appendix A-B.

Theorem 2 (Joint decoding): There exists an (M, n, )-code

for the unsourced K-user A-channel with PUPE satisfying

≤K

2

M+

`=1

KE"min(1,K

K−`M−K

`

k=1 η

η=η

¯pηp(k, `, η)!Ak)# (8)

and there exists an (M, n, )-code with JPE satisfying

≤K

2

M+

`=1

E"min(1,K

K−`M−K

`

k=1 η

η=η

¯pηp(k, `, η)!Ak)#.(9)

In (8) and (9),

¯pη=k!S(K−`, η)

(k−η)!kK−`Zη

(10)

with Zηbeing a normalizing constant ensuring that

Pη

η=η¯pη= 1. Here η,max{0, k −`}and η,min{k, K −

`}. Finally

p(k, `, η) = k

q`

π(k, `, η)(11)

where the ﬁrst factor (k/q)`is the probability that the `

non-transmitted codewords hit one of the koutput symbols,

and π(k, `, η)is the conditional probability that the `non-

transmitted codewords hit the remaining k−ηsymbols given

they all hit one of the koutput symbols. Note that the

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Finite-BlocklengthResultsfortheA-channel:ApplicationstoUnsourcedRandomAccessandGroupTestingAlejandroLancho,AlexanderFenglerandYuryPolyanskiyAbstractWepresentnite-blocklengthachievabilityboundsfortheunsourcedA-channel.Inthismultiple-accesschannel,usersnoiselesslytransmitcodewordspickedfromacommonco...

展开>> 收起<<

Finite-Blocklength Results for the A-channel Applications to Unsourced Random Access and Group Testing.pdf

共11页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Finite-Blocklength Results for the A-channel Applications to Unsourced Random Access and Group Testing

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: