InTech uses cookies to offer you the best online experience. By continuing to use our site, you agree to our Privacy Policy.

Computer and Information Science » Communications and Security » "Trends in Telecommunications Technologies", book edited by Christos J Bouras, ISBN 978-953-307-072-8, Published: March 1, 2010 under CC BY-NC-SA 3.0 license. © The Author(s).

Chapter 14

Novel Multiple Access Models and Their Probabilistic Description

By Dmitry Osipov
DOI: 10.5772/8483

Article top

Novel multiple access models and their probabilistic description

Dmitry Osipov1

1. Introduction

Nowadays as both the number of subscribers of the wireless services and the amount of data transmitted via the aforesaid services are growing rapidly multiple access techniques are becoming of special urgency for specialists in the field. Frequency Hopping technique appears to be one of the most promising paradigms for the next-generation multiple access system design.

In conventional frequency hopping the entire available frequency band is divided into N subbands (following the terminology used in Zigangirov, 2004 we shall further on refer to the set of all subbands available to the user as a hopset.). Each user’s transmitter chooses one of the N subbands in a pseudorandom manner and transmits a signal via the chosen subband using a conventional modulation technique (for the most part FSK is used). In the multiple access theory it is common to refer to each change of the subband in use as a hop. The process of switching between the subbands (which can be also interpreted in terms of assigning subbands to the users) is called frequency hopping. Frequency Hopping can be easily combined with the OFDM technique, which enables to reduce the distortion considered by both fadings and impulse noise (Note that OFDM is the fundamental technique for the most of the advanced telecommunications systems).

Frequency hopping (assigning subbands to the users) can be either coordinated (this means that when choosing a code sequence for each user, we use knowledge about other users; therefore, this scheme is mostly used for the downlink transmission) or uncoordinated. The uncoordinated frequency hopping has a number of advantages (enables to realize random multiple access, is well protected from eavesdropping or intentional jamming, and does not require elaborated protocols, which are inevitable in a system with coordinated subcarrier assignment) and is used, as a rule, for the uplink transmission. We shall consider uplink transmission, and, hence, uncoordinated subcarrier assignment strategies. In turn, these strategies can be divided into two groups. Methods of the first group exploit code sequences specially designed for multiple access systems and satisfying certain requirements. The second group includes methods where subcarrier numbers are assigned to users pseudorandomly. In what follows a FH CDMA system using a method from the second group will be considered.

The proposed chapter is aimed at introducing to the readers a novel class of FH CDMA systems; these are Dynamic Hopset Allocation FH CDMA (DHA FH CDMA) systems. This class has been initially introduced in Zyablov & Osipov, 2008. As can be seen from its name the main difference between the conventional FH CDMA and the proposed class of Dynamic Hopset Allocation FH CDMA is that the hopset allocated to each user varies in time.

2. DHA FH: transmission technique

Let us now consider the basics of the DHA FH CDMA in more detail. Consider a multiple access system where K active users transmit data to the base station through a channel divided with the help of the OFDM technology into Q frequency subchannels; the transmission is asynchronous and uncoordinated (the latter means that neither of the users has information about the others). It is assumed that all the users transmit binary β -tuples. In the course of the transmission of each consecutive tuple the subchannel number generator assigned to the user under consideration chooses (in a random manner) q=2β subchannels out of Q subchannels. Each tuple (or a part of the tuple) that is to be transmitted by the aforesaid user within the frame is mapped into the number of the subchannel, via which the signal is transmitted.

In what follows we shall assume that in the system under consideration optimal power control is used. The latter means that the amplitudes of all the signals from distinct users are equal at the receiver side. Furthermore we shall assume that in the system under consideration optimal phase estimation and prediction mechanism is used (i. e. phases of all the signals from distinct users are known to the base station). Hereinafter we shall consider a multiple access system, which uses an Additive White Gaussian Noise channel. In this case near optimal power control and phase estimation can be done fairly easily since both transmission ratio and phase of the signal from a certain user depend only on the distance between the transmitter and the receiver. The latter can be measured either by using pilot sequences or by analyzing information obtained from the downlink channel (which seems preferable since it is more convenient for implementing open loop power control and enables to avoid other users interference). Note, however, that in either case the transmitted signal is affected at least by the background noise, thus even in this case only near optimal power control and phase estimation can be maintained.

It is assumed that the base station is equipped with the subchannel numbers generator synchronized with that of the active user. The latter means that within the scope of the reception of the respective tuple subchannel numbers generator of the base station produces the very same subchannel numbers vector that has been generated by the subchannel numbers generator of the user under consideration. Note that this assumption is not restrictive since synchronized generators are an essential part of any conventional FH CDMA system. Thus we simply replace a generator producing random numbers with a generator producing random vectors.

Assume now that there is an eavesdropper, who intends to reconstruct the signals sent by the active users. In the conventional FH CDMA system eavesdropping is considered to be a complicated task since it is preassumed that the hopping sequences are not known to the eavesdropper. However even if the hopping sequence is not known to the user it is still possible to reconstruct the transmitted signal. Note that the DHA FH CDMA system is much more eavesdropping proof than the conventional one (since to reconstruct a tuple an eavesdropper needs not only to detect, which subchannel has actually been used to transmit a signal, but also to detect its position in the hopset, the latter being known only to the active user under consideration).

However, the introduction of the aforesaid new class of FH CDMA systems results in the emergence of a whole complex of problems. The problem of giving a suitable probabilistic description appears to be one of the most urgent ones. The present chapter is aimed at solving this problem. The latter is to be done using characteristic function apparatus. Since the probabilistic description depends on the reception strategy two different strategies, i. e. threshold reception and MAXP reception, will be considered. For each of the above mentioned reception strategies an analytical expression will be given. The results to be obtained will enable to get new insights into the whole complex of problems of novel types of CDMA systems study and development.

3. DHA FH OFDMA system with threshold reception: system model and probabilistic description

A receiver, equipped with a subchannel number generator synchronized with the subchannel number generator of this user, compares values of projections of signals received through these subchannels onto a direction denoted by the phase of the signal from the respective user at the receiver side with a ceratin threshold (in what follows, we shall assume that the base station knows the phases of complex transmission coefficients of all the subchannels; i. e., the system exploits an ideal estimation an prediction mechanism for frequency characteristics of the channel). If threshold crossing is detected in only one subchannel, a tuple corresponding to the subchannel where the threshold crossing was registered, is accepted. Otherwise, an erasure decision is made. If a symbol other than the transmitted one is accepted, we say that an error has occurred. The block diagram of the DHA FH CDMA system with a threshold receiver is shown in Figure 1.

media/image5.jpeg

Figure 1.

DHA FH OFDMA system with threshold reception: block diagram.

Due to the above-made assumption on the availability of an ideal power control in the system, the signal of each user at the receiver end can be represented by a vector of a unit amplitude with a random phase uniformly distributed on the circle [0,2π] . Since all the users transmit data asynchronously, the duration of interaction of a fixed user with other active users (we call them "interfering" users) is a random variable uniformly distributed on [0,T] . Therefore, components of the noise from each "interfering" user can be represented by vectors with amplitudes uniformly distributed on [0,1] and random phases uniformly distributed on [0,2π] .

Let us consider the projection of an output of the j-th subchannel onto a unit-amplitude vector with phase jj (here jj is the phase of the signal from the user under consideration at the receiver end.) The projection is of the form:

yj=aj+k=1Kjrjkcos(φjk)+nj
(1)

where aj is the amplitude of the signal transmitted by this user through this

subchannel

aj={1    j=j*0    jj*
(2)
Kj is the number of "interfering" users in the j-th subchannel; rjk is the amplitude of the noise caused by the interaction with the k-th "interfering" user, which is uniformly distributed on [0,1]; jjk=jjjk , where jk is the phase of the noise caused by the interaction with the k-th "interfering" user, which is uniformly distributed on the circle [0,2π] ; jj is the phase of the transmitted symbol at the receiver end, which is uniformly distributed on the circle [0,2π] ; and nj is the projection of a vector corresponding to the white Gaussian noise. Since the components of the white noise have the same variance, the value of the projection of the corresponding vector onto any direction is also normally distributed with the same variance. Since the phases of both the noise and the transmitted symbol are uniformly distributed on the circle [0,2π] , the phase difference jjk is also uniformly distributed on [0,2π]

Since for parameters that adequately describe modern multiple access systems, the probability of a collision of multiplicity greater than two is much less than the probability of a collision of multiplicity two (see Appendix A.) further on only collisions of multiplicity two will be considered; the occurrence probability of such a collision is set to be equal to the collision occurrence probability

where p0 is the probability of no collision. Since transmission is asynchronous, during the time when a user transmits a symbol, each of the other active users chooses two subchannels. Therefore, the probability of no collision is given by

p0=(Q1Q)2(K1)
(4)

and the projection is given by:

yj=aj+λcos(α)+nj
(5)

An expression for the density function of the value of the projection of the noise from the k-th “interfering” user onto a given vector follows from a formula due to Feller, 1971 and is of the form:

f(z)=1πln(1+1z2|z|)
(6)

Finding an analytic expression for the density function of yj directly (for instance, using the convolution theorem) presents considerable difficulties. By definition Lukacs, 1987, the characteristic function of a random variable Z=λcos(α) is the expectation of the function y=φξ(λ,α)=eiξZ(λ,α) . This expectation can be defined in a straightforward manner:

gZ(ξ)=φξ(λ,α)f(λ,α)dαdλ
(7)
here f(λ,α)={12π     λ[0,1]α[0,2π]0     otherwise is the joint probability density function.

Taking into account the domain of definition of the function, the characteristic function can be represented as follows:

gZ(ξ)=0102πeiξλcos(α)2πdαdλ
(8)

Note that

Jo(ξλ)=12π02πeiξλcos(φ)dφ
(9)

is nothing but the zero-order Bessel function of the first kind of the variable υ=ξλ Watson, 1945. Integrating the series expansion of this function term by term, we obtain:

g1(ξ)=01(1+k=1(i)2k(ξλ)2k22k(k!)2)dλ=1+k=1(i)2kξ2k(2k+1)22k(k!)2
(10)

By a property of characteristic functions, the desired density function of the variable y is of the form:

f(y,a,σ)=eiξygZ(ξ)χ(ξ,a,σ)dξ
(11)

where χ(ξ,a,σ) is the characteristic function of a normal distribution with mean a and variance σ . Taking into account eiξyξnχ(ξ,a,σ)dξ=1(i)ndnη(y,a,σ)dyn we obtain

fs(y,a,σ)=k=11(2k+1)22k(k!)2d2kη(y,a,σ)dy2k
(12)

here η(ξ,a,σ) is the probability density function of a normal distribution with mean a and standard deviation σ

This function characterizes the density function of the value of the projection of a subchannel output provided that a collision of multiplicity two occurred in the subchannel (i. e., there was one “interfering” user) and that the user under consideration transmitted a signal of amplitude a through this subchannel.

Thus, the conditional density function of the variable at the output of a subchannel, through

which the user transmitted a symbol of amplitude a, is of the form:

μ(y,a,σ)=η(y,a,σ)p0+(f(y,a,σ)(1p0))
(13)

Below we are using the obtained probability density function to solve the detection problem in the described system.

3.2. DHA FH OFDMA system with threshold reception: threshold choice and analytical expressions for error and erasure probabilities

Symbol detection in the described system boils down to choosing between two hypotheses:

H0: the user did not transmit any symbol through this subchannel (a = 0);

H1: the user transmitted a symbol through this subchannel (a = 1).

The maximum likelihood condition implies that:

iffs(y|1)f(y|0)spa(0)pa(1)H1isacceptediffs(y|1)fs(y|0)pa(0)pa(1)H0isaccepted
(14)

where L=fs(y|1)fs(y|0) is the likelihood ratio, and pa(1)=1q

pa(0)=1pa(1)=q1q
(15)

a priori probabilities. Hence we obtain,

fs(y|1)f(y|0)s=q1
(16)

Our goal is to find the threshold value y. The value will be found by solving the nonlinear equation (3.14) numerically.

Direct computation of the likelihood ratio on the left-hand side of (3.14) seems to be difficult. At the same time, numerical values of the conditional density function at any point can be computed using finitely many terms of the above-given expansion. To estimate these values to a given degree of accuracy, it suffices to find an expansion term, whose absolute value at a given point is less than the accuracy parameter and check that the same holds for the subsequent term too. Thus, the threshold finding problem is reduced to solving a nonlinear equation (3.14) which can be done numerically using specialized software packages. The solution of the equation (3.14) y^ is the optimal (in a maximum a posteriori sense) threshold value.

Hereinbefore we have treated the process of assigning subchannels to the users in terms of series of random trials. Strictly speaking, when considering a set of subchannels, we are to consider the parameters of each consecutive test run as dependant on outcomes of the previous test runs. Consider the i-th subchannel of the q subchannels chosen by the subchannels number generator. Let us assume that k users were transmitting in i-1 previously considered subchannels. The probability of collision is to be estimated as

pJ=(Qi1Qi)2(K1)k
(17)

However, since iqQ and

(Qi1Qi)2(K1)k(Q1Q)2(K1)
(19)

Thus, in what follows we shall assume that the probability of collision in a certain subchannel does not depend on the situation in other subchannels.

The error probability is the probability that the threshold is not crossed in the subchannel, through which the user under consideration has transmitted a symbol and at the same time the threshold is crossed in one of the subchannels, where this user has not transmitted any signal (and only in it). This probability can be written as:

perr(q1)y^fs(y|1)dyy^+fs(y|0)dy(y^fs(y|0)dy)q2
(20)

To find the erasure probability, we shall find the probability of correct reception, i. e., the probability that the threshold crossing occurs only in the subchannel, through which the user has transmitted a symbol. This probability is described by the relation:

pcory^+fs(y|1)dy(y^fs(y|0)dy)q1
(21)

Since correct reception, error, and erasure form an exhaustive group of events, we may claim that the erasure probability is

pers=1pcorperr
(22)

Note that the obtained expressions are approximate (due to the aforementioned assumptions). More exact expressions can be easily obtained using the same method. However in this case the obtained expressions will have a much more cumbersome form.

4.1. DHA FH OFDMA system with a MAXP receiver: system model and probabilistic description

In the previous section a threshold reception has been considered; i. e. a receiver, equipped with a subchannel number generator synchronized with that of the user under consideration, was to compare values of the projections of the signals received from the subchannels with a certain threshold and take a decision on the symbol sent by the user under consideration. Hereinafter a far more simple and intuitive reception strategy will be used; i. e. the receiver is to compute the projections of the signals from the respective subchannels and to choose the subchannel with a maximum projection. In what follows we shall refer to this receiver as a MAXimum Projection receiver (a MAXP receiver). The block diagram of the DHA FH CDMA system with a threshold receiver is shown in Figure 2.

media/image55.jpeg

Figure 2.

DHA FH OFDMA system with a MAXP receiver: block diagram.

Note that in DHA FH CDMA with a threshold receiver an optimal threshold value is to be precomputed in advance. Moreover, as can be seen from the previous paragraphs, the optimal threshold value depends on the number of active users and SNR. In DHA FH CDMA with a MAXP receiver, on the other hand, neither additional computation nor any kind of side information is needed. It should be noted, however, that for DHA FH CDMA system with a threshold receiver and DHA FH CDMA system with a MAXP receiver different types of outer codes are to be used. In a DHA FH CDMA system with a threshold receiver outer codes capable of correcting erasures (a number of low density codes suited for the task were introduced recently) are to be used, whereas in a DHA FH CDMA system with a MAXP receiver only error correction is needed (woven and woven turbo codes seem to be the best solution in the case).

Let us consider a difference:

δj*j=yj*yj=a+j*ρj*j+n
(23)

here yj* is the projection of the output of the j* -th subchannel (i. e. the subchannel, via which the user under consideration has actually transmitted a symbol); yj is the projection of the output of the j -th subchannel ( jS,jj* )

Note that for parameters that adequately describe modern multiple access systems, the probability of a collision of multiplicity greater than two is much less than the probability of a collision of multiplicity two. Therefore, hereinafter we are considering the case of a collision of multiplicity two only. Correspondingly we are to consider several distinct situations:

a. A collision has occurred both in the j* -th subchannel and in the j -th subchannel (see Figure 3).

media/image62.jpeg

Figure 3.

“case a.” (three interfering signals): diagram.

Then ρj*j is given by:

ρj*j(c*,s,c)=λcos(α)μcos(β)κcos(φ)
(24)

b. A collision has occurred in the j* -th subchannel and a user has transmitted a symbol via the j -th subchannel. (see Figure 4).

media/image65.jpeg

Figure 4.

“case b.” (two interfering signals): diagram.

Then ρj*j is given by:

ρj*j(c*,s,c¯)=λcos(α)μcos(β)
(25)

c. A collision has occurred in the j* -th subchannel and none of the users has transmitted a symbol via the j -th subchannel (see Figure 5).

media/image67.jpeg

Figure 5.

5. “case c.” (one interfering signal): diagram.

Then ρj*j is given by:

ρj*j(c*,s¯,c¯)=λcos(α)
(26)

d.A user has transmitted a symbol via the j -th subchannel and no collision has occurred either in the j -th subchannel or in the j* -th subchannel (see Figure 6).

media/image69.jpeg

Figure 6.

6. “case d.” (one interfering signal): diagram.

Then ρj*j is given by:

ρj*j(c¯*,s,c¯)=μcos(β)
(27)

e. A collision has occurred in the j -th subchannel and no collision has occurred in the j* -th subchannel (see Figure 7).

media/image71.jpeg

Figure 7.

7. “case e.” (two interfering signals): diagram.

Then ρj*j is given by:

ρj*j(c¯*,s,c)=μcos(β)ηcos(φ)
(28)

f.No collision has occurred in the j* -th subchannel and none of the users has transmitted a symbol via the j -th subchannel (see Figure 8).

media/image73.jpeg

Figure 8.

8. “case f.” (no interfering signals): diagram.

Then ρj*j is given by:

Note that the distribution of ρj*j does not depend on the sign of the component since all the phases are distributed uniformly on [0,2π] . Therefore ρj*j(c*,s¯,c¯) and ρj*j(c¯*,s,c¯) have the same distribution.

Moreover the probability density function of differences δj*j(c*,s¯,c¯)=aj*+λcos(α)+n and

δj*j(c¯*,s,c¯)=aj*μcos(β)+n
(30)

can be obtained using the same method we have used to obtain the projection yj* and is given by

f(y,a,σ)1=fδj*j(c*,s¯,c¯)(y,a,σ)=fδj*j(c¯*,s,c¯)(y,a,σ)=k=11(2k+1)22k(k!)2d2kη(y,a,σ2)dy2k
(31)

here η(ξ,a,σ2) is the probability density function of a normal distribution with mean a and standard deviation σ2

Analogously ρj*j(c*,s,c¯) and ρj*j(c¯*,s,c) have the same distribution. Since all the components in (4.3) and (4.6) are independent the characteristic function is simply the product of the characteristic functions of the components:

g2(ξ)=g1(ξ)g1(ξ)=1+m=1k=1(i)2k+2mξ2k+2m(2k+1)(2m+1)22k+2m(k!m!)2
(32)
g2(ξ)=1+t=1ξ2t22t(k=1t1(2k+1)(2t2k+1)(k!(tk)!)2)
(34)

The probability density function of differences δj*j(c*,s,c¯)=aj*+λcos(α)μcos(β)+n

and δj*j(c¯*,s,c)=aj*μcos(β)ηcos(φ)+n is given by:
f2(y,a,σ)=fδj*j(c*,s,c¯)(y,a,σ)=fδj*j(c¯*,s,c)(y,a,σ)=eiξyg2(ξ)χ(ξ,a,σ2)dξ
(35)
f2(y,a,σ)=t=0(d2tη(y,a,σ2)dy2t122t(k=1t1(2k+1)(2t2k+1)(k!(tk)!)2))
(36)

Similarly the characteristic function of δj*j(c*,s,c)=aj*+λcos(α)μcos(β)κcos(φ)+n

is given by:

g2(ξ)=g1(ξ)g1(ξ)g1(ξ)=1+k=1m=1w=1(i)2k+2m+2wξ2k+2m+2w(2k+1)(2m+1)(2w+1)22k+2m+2w(k!m!w!)2
(37)

And the probability density function of difference δj*j(c*,s,c) is

f3(y,a,σ)=fδj*j(c*,s,c)(y,a,σ)==t=0(d2tη(y,a,σ2)dy2t122t(k=1tm=1k1(2k+1)(2m+1)(2t2k2m+1)(k!m!(tkm)!)2))
(38)

Note that difference δj*j(c*,s,c)=aj*+n is simply a Gaussian viable.

4.2 DHA FH OFDMA system with a MAXP reception: error probability

To find the error probability let us consider the probability of correct reception. Correct reception is possible if (and only if ) δj*j0jS,jj* . As can be seen from what has been said the distribution of the differences δj*j depend on how many active users are there in the respective subchannels. Moreover, as has already been mentioned, we shall confine ourselves to the case of collisions of multiplicity two (in the subchannels chosen by the subchannel number generator of the active user under consideration). Let us consider the following situation: in the rest q1 subchannels (i. e. in all the subchannels chosen by the subchannel number generator of the active user under consideration but for the one in use) there are exactly a subchannels where a collision has occurred (i. e. in each of the a subchannels 2 users were transmitting) b subchannels where users were transmitting but no collision had occurred (i. e. there was 1 active user in each subchannel ) and c=q1ab subchannels where no users were transmitting any data.

The probability of such a situation is given by:

p(a,b,q,Q,Ξ)=(q1)!a!b!(q1ab)!(Qq)Ξ2aba=0[Ξ2]b=0Ξ2a(q1)!a!b!(q1ab)!(Qq)Ξ2ab
(39)

where Ξ is the total number of signals that can be transmitted via all the subchannels but for the one, via which the user under consideration has transmitted (see Appendix B.)

As has been already mentioned if the total number of active users amounts to K the number of signals that can interfere with the signal transmitted by the user under consideration is Κ=2(K1) due to the transmission asynchrony. Thus, we are to consider two distinct cases:

I. A collision has occurred in the subchannel, via which the user has transmitted a signal (this case obviously corresponds to the cases a.)-c.) from the previous section)

II. No collision has occurred in the subchannel, via which the user has transmitted a signal (this case corresponds to the cases d.)-f.) from the previous section)

Since we are considering collisions of multiplicity two only in case II, the number of interfering users is given by Ξ=2(K1) and in case I by Ξ=2(K1)1

To obtain the conditional probability note that in the abovementioned case, if a collision has occurred in the subchannel in use, we obtain a differences with pdf f3 b differences with pdf f2 and c=q1ab differences with pdf f1 . Thus, the conditional probability of error for the situation in question is given by:

pe(a,b,q|ς=1)=[1((0+f3(y,a,σ)dy)a(0+f2(y,a,σ)dy)b(0+f1(y,a,σ)dy)q1ab)]
(41)

If there is no collision in the subchannel in use we obtain a differences with pdf f2 b differences with pdf f1 and c=q1ab differences with pdf f0 . The conditional probability is then given by:

pe(a,b,q|ς=0)=[1((0+f2(y,a,σ)dy)a(0+f1(y,a,σ)dy)b(0+f0(y,a,σ)dy)q1ab)]
(42)

Thus, the probability of error is given by:

perra=0[K22]b=0(2(K1a)1)(pe(a,b,q|ς=1)pJp(a,b,q,Q,2(K1)1))++a=0[K12]b=02(K1a)(pe(a,b,q|ς=0)(1pJ)p(a,b,q,Q,2(K1)))for  K2
(43)

where pJ is the probability of collision (see (3.2)).

5. Conclusions and future work

Hereinabove a novel class of FH CDMA systems has been introduced: these are Dynamic Hopset Allocation FH CDMA systems. Two models with different reception strategies were considered: the DHA FH CDMA system with a threshold receiver and the DHA FH CDMA with a MAXP receiver. For both models a probabilistic description has been given using the approach based on characteristic function apparatus (for the DHA FH CDMA system with a threshold reception both a nonlinear equation for optimal threshold value and analytical expressions for error and erasure probabilities have been given; for the DHA FH CDMA with a MAXP receiver an analytical expression for the probability of error has been given).

However, even though several simplifying assumptions were used the obtained expressions are still complicated. Thus, obtaining rougher but less cumbersome expressions for the probability density functions of the random variables in question and respectively obtaining upper and lower bounds for error and erasure probabilities is one of the most important tasks. Moreover, it is to be mentioned that the expressions in question were obtained for the AWGN channel. Generalizing the obtained results for fading channel models (say, Raleigh, Nakagami ect.) is also a very important task. Obviously power control at the receiver side is unacceptable in this case. However, even in case of open loop nearly ideal power control it is to be taken into account that the power of a real life transmitter is bounded i. e. even in this case expressions for error and erasure probabilities will be different from those obtained for the AWGN channel.

Appendices

6. Appendix A

Let us show that the probability of collisions of multiplicities greater than two is much less than the probability of a multiplicity-two collision. To this end, consider the process of choosing subchannels for transmission by users as a sequence of independent trials. Due to asynchronicity, during the time when a user transmits a symbol, each other active user chooses two subchannels. Thus, the process of choosing subchannels for transmission by other active users is equivalent to a series of N = 2(K − 1) trials with “success” probability p = 1/Q (in this case, it is the probability that there is chosen the subchannel which is used by the user under consideration). Therefore, the probability that a collision of multiplicity m = k+1 occurs in a given subchannel is the probability that in a series of N = 2(K − 1) trials with “success” probability p = 1/Q there are precisely k successes. This probability is given by the Bernoulli formula:

pJ(m)=CNk(1Q)k(11Q)Nk
(44)

where pJ(1) is the probability of no collision. Consider the ratio:

κ=pJ(m2)pJ(2)
(45)

It is seen from the aforesaid that:

κ=pJ(m2)pJ(2)=k=2NCNk(1Q)k(11Q)NkCN1(1Q)1(11Q)N1=k=2NCNk(Q1)NkN(Q1)N1
(46)

hence we get:

κ=k=2NCNk(Q1)k+1N
(47)

For each term in this expansion, we may write:

CNk(Q1)k+1N=N!(Nk)!(k)!(Q1)k+1N=N(N1)(Nk+1)N(Q1)k1(k)!(N1(Q1)2)k1
(48)

thus, it is obvious that:

κk=2N(N1(Q1)2)k1
(49)

For any Q such that QN12 (and in real-world systems we have Q >> N), the expression on the right-hand side is a sum of a decreasing geometric progression starting with the second term:

κk=1N(N1(Q1)2)k11k=1(N1(Q1)2)k11=11N1(Q1)21
(50)

Note that 11N1(Q1)211QQN2

As we have already noted, in real-world systems we have QN . Therefore, we may claim that for any parameters that adequately describe modern systems, the formulated statement certainly holds.

Appendices

7. Appendix B

To obtain the probability of such a situation let us find the number of all sets complying with the abovementioned condition. To simplify the process let us treat the process of random subchannel choice performed by each of the active users in terms of assigning the interfering signals from other active users to the subchannels (the latter procedure is analogous to the classical examples with balls randomly placed into boxes). Let us again consider the subset of q1 subchannels (these are all the subchannels chosen by the subchannel numbers generator but for the one, via which the user under consideration has transmitted) where there are exactly a subchannels, to which 2 signals are assigned, b subchannels, to which 1 signal is assigned, and the rest of the subchannels are empty (i. e. no signal has been assigned to none of these subchannels). The number of ways to perform such an assignment is given by

N(a,b,q1)=(q1)!a!b!(q1ab)!
(51)

Now let us consider the process of the symbol transmission by the user under consideration. In what follows we shall assume that there are Ξ interfering signals and that the assignment for all the subchannels chosen by the subchannel numbers generator (but for the one, via which the user under consideration has transmitted) is performed in the very way that has been discussed above. Thus we still have to assign k=Ξ2ab signals to Θ=Qq subchannels (these are all the subchannels but for those chosen by the subchannel numbers generator of the user under consideration). However, from now on we needn’t confine ourselves to the case of collisions of multiplicity two. The process of “assigning” the remaining subchannels to the signals boils down to a series of k=Ξ2ab trails, each of which is a random choice of one of Θ=Qq subchannels. Thus the number of all the possible outcomes is

N(q,Q,Ξ|a,b)=(Qq)Ξ2ab
(52)

And the number of all the sets meeting the abovementioned requirements is given by

N(a,b,q,Q,Ξ)=N(a,b,q1)N(q,Q,Ξ|a,b)=(q1)!a!b!(q1ab)!(Qq)Ξ2ab
(53)

Apparently the probability of the occurrence of the aforesaid situation is the fraction of all the sets meeting the abovementioned requirements in the total number of sets. The latter is to be computed by summing N(a,b,q,Q,Ξ) over all possible values of a and

p(a,b,q,Q,Ξ)=(q1)!a!b!(q1ab)!(Qq)Ξ2aba=0[Ξ2]b=0Ξ2a(q1)!a!b!(q1ab)!(Qq)Ξ2ab
(55)

References

1 - W. Feller, 1971 An Introduction to Probability Theory and Its Applications 2 Wiley and Songs, 0471257095047125709-5, NY.
2 - E. Lukacs, 1987 Characteristic Functions., A Charles Griffin Book, 0-19520-578-2
3 - G. N. Watson, 1945 Theory of Bessel Functions, Cambridge Press, 0-52148-391-3
4 - K. Sh Zigangirov, 2004 Theory of Code Division Multiple Access Communication., IEEE Press, 0-47145-712-4 New Jersey.
5 - V. V. Zyablov, D. S. Osipov, 2008 On the optimum choice of a threshold in a frequency hopping OFDMA system.. Problems of Information Transmission, 44 2 2008, 91 98 , 0032-9460.