On a Multiple-Access in a Vector Disjunctive Channel Alexey Frolov and Victor Zyablov Vladimir Sidorenko and Robert Fischer Inst. for Information Transmission Problems Institute of Communications Engineering Russian Academy of Sciences University of Ulm Moscow, Russia Ulm, Germany Email: {alexey.frolov, zyablov}@iitp.ru Email: {vladimir.sidorenko, robert.fischer}@uni-ulm.de Abstract—We address the problem of increasing the sum rate model users are only allowed to transmit vectors of weight in a multiple-access system from [1] for small number of users. one). We suggest an improved signal-code construction in which in In [1], a signal-code construction for the multiple-access caseofasmallnumberofuserswegivemoreresourcestothem. 3 system using the A channel was introduced.The construction For the resulting multiple-access system a lower bound on the 1 relative sum rate is derived. It is shown to be very close to the was based on Kautz–Singleton (KS) codes [8]. For the re- 0 maximal value of relativesumratein [1] even forsmall number sulting multiple-access system a lower bound on the relative 2 of users. The bound is obtained for the case of decoding by sum rate was derived and it was shown that the bound n exhaustive search. We also suggest reduced-complexity decoding coincides with an upper bound asymptotically. The signal- a and compare the maximal number of users in this case and in J case of decoding by exhaustive search. code construction requires neither block synchronization nor 4 feedbackwhicharesignificantadvantagesofit.Alltheresults 2 I. INTRODUCTION wereobtainedin case ofdecodingbyexhaustivesearch.Sure, In this paper we consider a noiseless multiuser vector dis- thedecodingalgorithmisnotapplicableincase ofcodeswith T] junctive (logical OR) channel which is also called Z-channel. large dimensions. In [9], a reduced-complexity decoding of I This means that “1” is always transmitted correctly, and “0” KScodesbasedonReed–Solomon(RS)codeswassuggested. s. may be replaced by “1”. Let us denote the number of active It was done by a modification of the Guruswami–Sudan list c users by S, S 2. So forsome time τ the channelinputsare decoder [10] or the soft-input Koetter–Vardy [11] decoder of [ binaryvectors≥x(τ), i=1,2,...,S,and thechanneloutputat RS codes. Unfortunately the maximal number of active users i 1 time τ is an elementwise disjunction of vectors at input was much smaller in comparison to [1]. v Themajordisadvantageofthemultiple-accesssystem from 2 S [1]isasfollows.Incaseofsmall(incomparisontothenumber 5 y(τ) = x(τ). i ofsubchannels)numberofuserstherelativesumrate (orsum 8 i=1 _ rate per subchannel) is very close to zero. Our main goal 5 Themotivationtoconsiderthechannelmodelisasfollows. . in the paper is to increase the relative sum rate for a small 1 Consider a communication scheme which uses M-ary pulse number of users. To achive this we propose a new signal- 0 positionmodulation(PPM).Inthiscasethechannelconsistsof 3 code construction in which in case of small number of users M subchannelswhichcorrespondtoeitherfrequencies[2],[3] 1 we will give more resourses to them. Let the channel consist : ortimeslots.Totransmittheith elementofanM-aryalphabet of Q subchannels. We divide all the range of subchannels v theuserneedstotransmitenergy(e.g.,ashortpulse)inthe ith i into nonoverlapping subranges of q subchannels and give X subchannel.We can say that the M-ary symbol is transmitted m=m(S) subranges to each user. r as a binary vector of length M and weight one. The detector Our contribution is as follows. We propose a new signal- a at the receiver measures the energy in the ith subchannel and code construction, which is an improvement of signal-code decidesif“1”or“0”wastransmittedbycomparingtheenergy constructionfrom[1]. A lowerboundon the relativesum rate withthethreshold.Inthiscasetheprobabilityofreceiving“1” is obtained and shown to be very close to the maximal value as“0”ismuchsmallerthentheprobabilityofreceiving“0”as of sum rate in [1] even for small number of users. We find “1”asweneedtosuppresstheenergyinthefirstcase.Thuswe the maximal number of active users in the system. Finally, use a vector disjunctive channel model as an idealized model reduced-complexity decoding is suggested and the maximal for this or similar communication schemes. number of users is found in this case. The channelmodelis similar to the A channel[4], [5], [6], [7], but in the present paper we remove the restriction on the II. BASIC SIGNAL-CODE CONSTRUCTION weight of the vectors transmitted by users (in the A channel A. Kautz-Singleton Codes The Kautz-Singleton code is a concatenation of an outer The work of A. Frolov has been supported in part by the RFBR grant 12-07-31035. V.Sidorenko isonleavefromIITPRAS,Moscow,Russia. (n,k)-code over Fq and the following inner code. Let us enumeratetheelementsofthefieldF insomeorderasfollows C. Reception q F = α ,α ,...,α . Thebasestationsequentiallyreceivesmessagesfromallthe q 1 2 q users.Letusconsidertheprocessofreceivingamessagefrom The inner code one-to-o(cid:8)ne maps every fi(cid:9)eld element αi ∈Fq the ith user. We assume that the base station is synchronized to a binarycolumnvectorof length q havinga single nonzero with transmitters of all the users. This means that t columns element at the ith position. The vector positions are counted thatcorrespondtoacodewordsentbyithuserareknownatthe from 1 to q. receiver. At receivingof each column the inverse permutation Example 1. Let c= α ,α ,α ,α ,α ,α be a codeword is performed. Thus, we obtain a matrix 2 4 6 1 2 5 of (6,2)overF . TheRS codewordc willbe encodedinto 7 RS (cid:2) (cid:3) a KS codeword C as follows 0 0 0 1 0 0 Yi =Ti  Xj, ∨  1 0 0 0 1 0  j=j1_6=,..i.,S  0 0 0 0 0 0     where Ti is a matrix corresponding to a KS codeword (Ci) C= 0 1 0 0 0 0 . transmittedby the ith userand matrices Xj,j =1,...,S, j =   6  0 0 0 0 0 1  i, are the results of another users activity. Note that matrices    0 0 1 0 0 0  Xj may not contain whole codewords sent by another users.      0 0 0 0 0 0  Example 2. Let m=1, Q=q =7. If, for example, the code     matrixCfromExample1wastransmittedthenwecanreceive B. Transmission the following matrix Y i Let us recall that the channel consists of Q subchannels. A time interval during which one vector of length Q is 0 0 0 1 0 1 transmittedwillbe called a tact. Assumethatallthe usersuse 1 1 1 0 1 1 thesamealphabet:symbolsofF .Assumealsothateachuser   q 0 0 0 0 0 0 is given m subranges of q subchannels and the transmission   duration (in tacts) is t. Yi = 0 1 0 1 0 0 .   Each user encodes information to be transmitted with the  0 0 0 0 1 1    helpof a (n=mt,k,d)code (allusersuse thesame code).  0 1 1 0 1 0  C   Consider the process of sending a message by the ith user.    0 0 0 0 0 0  We denote the codeword to be transmitted by ci. Let Ci be a     KS codeword of size q mt correspondingto c . Then C is i i We see thatthechanneldoesnottouchthe“1”s ofthematrix splittedintomdisjointp×artsC(ij),j =1,2,...,m,ofsizeq×t C but replaces 8 zeros by “1”. and each of the parts is sent in the corresponding subrange. The subranges are allocated dynamically. For this purpose Thedecodingproblemisthiscaseisequivalenttodecoding permutations of length Q are used. Permutations used by a problem for KS code. For our basic signal-code construction current user are known to nobody except for a “transmitter- we use the decodingbyexhaustivesearch.Considerthe code- receiver” pair. word cl C. We needto constructa matrix Tl corresponding ∈ So the transmission can be seen in such a way. The word to cl in the manner described above. Since the described C is splitted into m parts multiple-access system uses a disjunctive channel all the i elements of the matrix at the channeloutputcorrespondingto Ci = C(i1)C(i2) ... C(im) . the codewordsent by the ith user will be non-zero.Therefore, q mt Then a matrix Ti ishformed i × tthhee iatshsuumseprtiisontrutheatonthlyeicfotdheewcoornddcitlio∈nCfowlloawsstransmitted by C(1) i T Y =T , (1)  C(2)  l∧ i l i . where is an element-wise conjunction of matrices. T = .  . i  .  To d∧ecode we need to check the condition (1) for all the    C(m)  words of . If the list of codewords satisfying the decoding  i  conditionCconsists of only one word, then the decoderoutputs  0   Q×t the word; if the list of codewords consists of several words Before sending a binary vector, a permutation of its ele- then the decoderoutputsa decodingfailure (decodingerror is ments is made (a new permutation is used for each vector). not possible in this case). In what follows we assume the permutations to be chosen equiprobably and independently from the set of all the Q! Remark1. Note,thatthepresenceofablocksynchronization possible permutations. is not need here like for the system from [1]. Remark 2. In a real system for permutations to be known E. Minimal number of tacts both on the transmitter and the receiver it is advisable to use In this paragraph we estimate the minimal number of pseudorandom number generators, which are a part of any tacts t needed to transmit k information symbols with given system based on frequency hopping [12]. probability of failure (p ). Let Q, q, S, m, k and p be fixed. r r From Theorem 1 we see that if D. Probability of failure klog q log p Let us estimate the probability p of decoding failure for d 2 − 2 r, (2) the ith user. Let β =1 1 m S∗−1. ≥ −log2β − − Q then p <p . We choose the smallest d satisfying (2), i.e. (cid:16) (cid:17) r Theorem 1. ∗ klog q log p n d= 2 − 2 r . p∗ ≤ A(W)βW <qkβd, (cid:24) −log2β (cid:25) W=d X (cid:2) (cid:3) In accordance to the Gilbert–Varshamov bound if n, d and where A(W) is the number of codewords of weight W in the k satisfy the inequality code C. d 2 Ti coPrrroeospf:onLdetttoheit.ithThueserexsiesntednacecoodfeawtolredascti,olneet tchoedmewatorridx n≥k+logq"Xi=−0(cid:18)n−i 1(cid:19)(q−1)i#, c =c such that the decoding condition follows for a matrix ∗ 6 i thenthereexistacodewithsuchparameters.Thus,wechoose T corresponding to it is sufficient for the decoder to output ∗ n in such a way a failure. Consider some codeword c′ = ci and let D = d(ci,c′). log q The codeword c will be includ6 ed in the list of codewords n= 2 (k+d 1) . ′ log q 1 − satisfying the decodingconditionif and only if a matrix T is (cid:24) 2 − (cid:25) ′ covered by “1”s in Y . Nowweobtaintheestimateontheminimalnumberoftacts i We can state that al least n D of n positions to be needed in this case: − checkedarenon-zeroascodewordsc andc coincideonthese ′ i n positions. Thus a codeword c will be included in the list if t = ′ m the remaining D positions are non-zero. l lmog q k(log q log β) log p Let us consider one column and let the column contain l = 2 2 − 2 − 2 r . log q 1 m( log β) of D positions (which should be checked) of a codeword c. (cid:24) 2 − (cid:18) − 2 (cid:19)(cid:25) ′ Let us enumerate these positions. We are interested in the F. Maximal number of users probability P l A , where A is an event consisting j=1 j j Let Q, q, m, t, k, d and p be fixed. In this paragraph we r in the fact tha(cid:16)tSthe posi(cid:17)tion with number j is covered. The estimate the maximal number of users for which p < pr. probability can be calculated as follows ∗ Directly from Theorem 1 we obtain l ln 1 √dpr P Aj=P(A1)P(A2|A1)·...·P(Al|A1...Al−1). S − − qR/δ +1, j[=1 ≤ ln(cid:16) 1 m (cid:17)   − − Q Notethatasrandomindependentequiprobablepermutations (cid:16) (cid:17) where δ =d/n, R=k/n. are used And thus P(A )=β, 1 ln 1 √dpr and S − − qR/δ +1. (3) P(Ab|A1...Ab−1)6β, b=2...l. max ≥ −ln(cid:16) 1− mQ (cid:17)  (cid:16) (cid:17)  Thus, we obtain Remark 3. Using the inequalities for logarithm l P A 6βl. x j x ln(1 x) | | ,   | |≤− −| | ≤ 1 x j=1 [ −| |   we obtain As a result the probability of a codeword c to be included ′ in a list is less or equal to βD. After getting a sum over all S Q 1 √dpr +1. the codewords (except c ) we obtain the needed result. max ≥ m − qR/δ i (cid:22)(cid:18) (cid:19) (cid:23) G. Sum rate Now we derive an asymptotic estimate of a sum rate. Requiring p to decrease exponentially with n (in other Let us introduce some notions. The rate for one user (in words, assumin∗g p = 2 cn, c > 0) and assuming that k bits per tact) r − is chosen such that k , k =o(Q), we obtain k m →∞ m R (Q,q,S,m,k,p )= log q. log q k log q log β i r t 2 t 2 2 − 2 , (4) ∼ log q 1 m log β c Byanalogywiththerateofasingleuser,wedefinethesum (cid:18) 2 − (cid:19) (cid:18) − 2 − ′ (cid:19) rate of all active users as the amount of information (in bits) where c′ =cloglog(q2q1). transmitted in a system during one tact. Since users transmit 2 − Remark 4. Note, that the transmission time t here is much information independently, this value can be computed as betterthanin[1].Alsonote,thatunlike[1]kshouldbechosen follows: large. k R (Q,q,S,m,k,p )=S log q. Σ r t 2 Let µ = m/Q, 1/Q µ 1/q. Let us introduce an ≤ ≤ Relative sum rate (the rate per subchannel) asymptotic quantity ρ(Q,q,S,m,k,p )= RΣ. ρ∞(q,S,µ,k,c)=Qlim ρ(Q,q,S,m,k,pr). (5) r Q →∞ After substituting (4) into (5) we obtain In Fig. 1 the dependency of ρ on m is shown. The param- ρ (q,S,µ,k,c) ρ (q,S,µ,c) eters are chosen as follows: Q = 4096, q = 64, pr = 10−10, ∞ ≥ ∞ log q 1 k =120.We see thatthereis a maximumofrelativesum rate = Sµ(−log2β−c′)log q2 −log β. at some m. 2 − 2 Let us introduce one more quantity 0.5 ρ (q,S,c)= max ρ (q,S,µ,c) . ∗ 0.45 ∞ 0<µ 1/q ∞ ≤ 0.4 Let ε be an arbitrarilysmall po(cid:8)sitivevalue, the(cid:9)dependency of ρ (q,S,ε) is shown in Fig. 3. 0.35 ∗ ∞ ρ 0.3 0.7 0.25 0.6 0.2 0.5 0.15 0.4 0.10 10 20 30 40 50 60 70 m 0.3 Fig.1. Dependency ofρonm 0.2 q=64 0.1 q=256 Now define q=1024 00 200 400 600 800 1000 1200 1400 1600 1800 2000 ρ (Q,q,S,k,p )= max [ρ(Q,q,S,m,k,p )]. S ∗ r r 1 m Q/q ≤ ≤ Fig.3. Dependency ofρ∗∞ onS In Fig. 2 the dependency of ρ on S is shown. The ∗ parameters are chosen as follows: Q = 4096, p = 10 10, r − Let µˆ =1 S−1 1, then k is chosen so that klog q =720 (bits). − 2 2 q ρ (q,S,µˆ,c), µˆ< 1 0.7 qq==62456 ρ∗∞(q,S,c)≥( ρ∞(q,S,1/q,c), otherqwise 0.6 q=1024 ∞ Remark 5. Note, that the condition µˆ < 1 holds when q 0.5 1 S > +1, 0.4 log (1 1/q) ρ* − 2 − 0.3 so after strengthening it we obtain 0.2 S >qln2+1. 0.1 Remark 6. Note, that 00 1000 2000 3000 4000 5S000 6000 7000 8000 9000 10000 ρ (q,S,µˆ,ε) (1 ε′)log2q−1ln2, ∞ ≥ − log2q+1 Fig.2. Dependency ofρ∗ onS where ε =Sε. ′ III. REDUCED-COMPLEXITY DECODING We see that the number of users in case of concatenated construction is smaller in comparison with the decoding by As in the proposed scheme k should be chosen large, then the exhaustive search over qk codewords is not applicable exhaustive search. But at the same time we significantly gain in the complexity of decoding. in practice. In this section we propose a reduced-complexity decoding for the signal-code construction. IV. CONCLUSION Let us choose the code of length n=mt to be concate- C In the present paper, a novel signal-code construction for nated, i.e., = , where is an outer (m,k ,d )- C CO♦CI CO O O a multiple-access system using a disjunctive vector channel code over GF(qkI), CI is an inner (t,kI,dI)-code over is proposed. The construction is an improvement of signal- GF(q). code construction from [1] and it also requires neither block We will decode the code in such a way. First we will synchronization nor feedback. The main advantage of the decodealltheinnercodesindependentlybyexhaustivesearch signal-code construction in comparison to the construction (as described above). We choose k to be small to have I from [1] is that the sum rate in case of small (in comparison small number of words. Then we will correct the erasures by to the number of subchannels) number of users is increased. the outer code. In what follows we assume that the erasure To achive this we divide all the range of subchannels into correction is done by means of gaussian elimination (the nonoverlappingsubrangesofsubchannelsandgivem=m(S) complexityisO(m3))togettheoreticalresults,butinpractise subranges to each user, where S is the number of users. A itisbettertousecodeswithsimpledecodingalgorithms(e.g., lowerboundontherelativesumratefortheresultingmultiple- low-density parity-check (LDPC) codes). access system is obtained and shown to be very close to the Letusdenotebyp(I) theprobabilityoffailureforoneinner maximal value of sum rate in [1] even for small number of ∗ code. Then in accordance to the Chernoff bound users.Alowerboundonthemaximalnumberofactiveusersin m p min e−sdO 1+p(I)(es 1) . the system is derrived.These two boundsare obtained forthe ∗ ≤ s>0 ∗ − case of decoding by exhaustive search. Reduced-complexity n h i o Thus the largest value of p(I) for which the requirenment decoding is suggested. The maximal number of users for ∗ reduced-complexitydecodingiscalculatedandcomparedwith p <p is satisfied can be calculated as follows r ∗ the maximal number of users in the case of decoding by pˆ(I) =max m√presδO −1 , exhaustive search. ∗ s>0 es 1 (cid:26) − (cid:27) REFERENCES where δ is the relative minimum distance of , i.e., δ = O CO O [1] D.Osipov,A.Frolov,V.Zyablov. Multiple Access SystemforaVector d /m. O Disjunctive Channel. Problems of Information Transmission, vol. 48. After substituting of pˆ(I) to (3) we obtain the lower bound no.3pp.243–249,2012. onthemaximalnumbero∗fusersincaseofreduced-complexity [2] T. Tsang, M. El-Gamal. Ultra-Wideband (UWB) Communications Sys- tems: An Overview. In 3rd International IEEE-NEWCAS Conference, decoding pp.381–386, Jun.2005. [3] K.Witrisal,G.Leus,G.Janssen,M.Pausini,F.Troesch,T.Zasowski,J. ln 1 d√I pˆ∗(I) Romme.NoncoherentUltra-WidebandSystems.IEEESignalProcessess- − − qRI/δI ingMagazine, pp.48–66,July2009. Smax  (cid:18) (cid:19)+1. [4] S.-C. Chang, J. Wolf. On the t-User m-Frequency Noiseless Multiple- ≥ ln 1 m  Access Channel withandwithout Intensity Information. IEEETransac-  − − Q  tionsonInformation Theory,pp.41–48,Jan.1981.  (cid:16) (cid:17)  [5] L. Wilhelmsson, K. S. Zigangirov. On the Asymptotic Capacity of a   In Fig. 4 the dependency of the maximal number of users Multiple-AccessChannel.ProblemsofInformationTransmission,pp.12– on the rate of concatenated code is shown for Q=218, p = 20,1997. r [6] L. A. Bassalygo, M. S. Pinsker. Evaluation of the Asymptotics of the 10 10, m = 200, t = 50, q = 64, k = 1,2,3,4 . The − I { } Summarized Capacity of an m-Frequency t-User Noiseless Multiple- comparison with the decoding by exhaustive search is made. AccessChannel. ProblemsofInformationTransmission,pp.3–9,2000. [7] A. Han Vinck, K. Keuning. On the Capacity of the Asynchronous t- 8000 Userm-FrequencyNoiselessMultiple-Access ChannelwithoutIntensity ECxohnacuastetinvaet eseda, rkcI h= 1 Information. IEEETransactions onInformationTheory,pp.2235–2238, 7000 Concatenated, kI = 2 Nov.1996. 6000 CCoonnccaatteennaatteedd,, kkII == 34 [8] W.Kautz,R.Singleton. NonrandomBinarySuperimposedCodes. IEEE Transactions onInformation Theory,pp. 363–377, 1964. 5000 [9] V. Sidorenko, R. Fischer. Low-Complexity List Decoding of Reed- Smax4000 SonoloSmysotnemCso,dCedomPmulusneicPaotisoitnionanMdoCduoldaitniogn,.JaInn.9t2h1–In2t4.,IT2G013C,onMfeurneincche, Germany. 3000 [10] V. Guruswami, M. Sudan. Improved Decoding of Reed-Solomon and 2000 Algebraic-Geometry Codes. IEEE Transactions on Information Theory, pp.1757–1767, 1757–1767, Sept.1999. 1000 [11] R. Koetter, A. Vardy. Algebraic Soft-Decision Decoding of Reed- 00 0.05 0.1 0.15 Solomon Codes. IEEE Transactions on Information Theory, pp. 2809– R 2825,Nov.2003. [12] K. Zigangirov. Theory of Code Division Multiple Access Communica- Fig.4. Comparisonwiththedecoding byexhaustive search tion. IEEEPress,2004.