― ― MEMOIRS OF SHONAN INSTITIUTE OF TECHNOLOGY Vol. 44, No. 1, 2009 * 情報工学科 准教授 **情報工学科 元教授 1. Introduction
In digital transmission or recording, intersymbol interference yields distortion of a signal in which one symbol interferes with subsequent symbols. This unexpected phenomenon makes the transmission or recording less reliable because the previous symbols are affected by similar effect as noise. The intersymbol interference is, therefore, one of the prime causes of the code error [1],[2],[3]. The intersymbol interference is, in the simplest case, expressed by the following random power series.
(1) where {Xn} is a sequence of independent identically distributed random variables such that
(2) Here a sequence of probability variables {Xn} used is called the Bernoulli sequence, the probability distribution of the random power series in eq.(1) is also said to become the Bernoulli convolution function. The distributions function of X called the Bernoulli convolution is
(3) and has been studied for more than sixty years[3].
For 0 < a < 1/2, F(x) is a singular distribution and is a step function of Cantor type[5]. On the other hand, for 1/2 < a <1, no explicit formula for general a has not been obtained and
only an approximate calculation has been reported[3]. When , p = 1,2, ･ ･ ･ , however, the Bernoulli convolution is a spline of degree p and can be expressed in a closed form[7]. In this case the distribution function is completely continuous and its density function is obtained, too.
In this paper, by making use of our formula, the density function of the Bernoulli convolution is calculated whose results are illustrated in Fig.1 for p = 6,7, ･･･,11.The curves of the density function for p = 1,2, ･･･,5 has been reported in Ref.[3].
2. The explicit formula When a = 1/2 in eq.(1),
(4) It is clear that X is a uniform distribution on [0,1]. That is
(5) The characteristic function of X can express as
(6) The distribution function F1(x) becomes
(7)
While where p = 2,3, ･･･,ap = 1/2. Therefore,
(8)
Numerical Values of Bernoulli Convolution
Juro T
AKEZAKI*
and Hiroshi S
UGIYAMA**
Intersymbol interference is reported as a random power series with Bernoulli variables as coefficients. When the argument is the p-th root of 1/2, an explicit function is given. Here, numerical calculations of the distribution function for several values of p are presented.
Key words: inter-symbol interference, Bernoulli convolution, truncated power function, spline function,
湘南工科大学紀要 第44巻 第１号
― ―
Numerical Values of Bernoulli Convolution (TAKEZAKI・SUGIYAMA)
― ― where
(9)
and
(10) {Xmp+k} where m = 0,1,･ ･ ･ is a subsequcnce of {Xm} and
independent. Yk is the probability variables with a uniform
distribution on [0,1] similar to eq.(4) and also independent of
Y1Y2, ･ ･ ･ ,Yp. Thus the distribution function F1(x) of the
equation (8) is to be expressed as
(11) where * denotes convolution in Ref.[1]. The distribution of Yk is the uniform distribution on [0,bk] . While the
characteristic function p(t) of X is
(12) where
(13)
The Bernoulli convolution function is, therefore, to be expressed as the convolution of the uniform distribution of the p piece. As a result, it is easy to see the Bernoulli convolution function becomes the spline functions of degree p. Thus, the Bernoulli convolution function is the spline functions of degree p when . The distribution function Fp(x) can be
obtained by using this fact as follows in Ref.[6].
(14) in which
(15)
is called the truncated m - th power function. While, (16) {εl}and {xl}, l =1, ･･･, q are defined as follows:
The power set, that is, the set of all subsets of B = {b1,･･･, bp}
be
(17)
and we define xl to be the sum of all bi which belong to Cl and εl= ∓1 according to whether or not the number of elements
belonging to Cl is even or odd.
It is easy to see that constitutes a basis of the m - dimensional linear space of spline functions of degree p. The distribution function Fp(x) is clearly absolutely
continuous and its density function is
(18)
3. Numerical Calculation
The numerical results of the density function when p is 1,2,3,4 and 5 has been obtained in Ref.[3]. It is easy to obtain in succession the density function for small value of p but not for large value of p. However, in eq.(18) the density function is represented in a general formula as a spline and it allows the computation for larger values of p.
In practice the calculation of fp(x) for large values of p can
be performed in the manner introducing the combinations, since the term xl in eq.(18) is the sum of all bj which belongs
to Cl. Hence, the term xl consists of all possible subsets of k objects described in eq.(17), the problem is, therefore, to
obtain all k-combinations of a q elements set 2B of distinct
objects. That is, one can be required to obtain all possible subsets of B. To compute calculation in eq.(18), for simplicity, the equation (9) when can be rewritten in
(19) where the quantities b1, ･･･,bp are arranged in a decreasing
order,
(20) Although all combinations of the power set 2B can be easily
obtained by making use of the algorithm in Ref.[8], the sum of elements of each combination constituting xl is an unordered
set. One may be required for calculations to arrange q items in increasing order as follows:
(21) Arranging q items in increasing order by making use of the bubble sort[7], we compute the equation (18) up to p=11. Although the algorithm calculating the value xl is based on
a complicated recurrence relation, the procedure given in Ref.[7] yields a simple computer program.
湘南工科大学紀要 第44巻 第１号
― ―
Numerical Values of Bernoulli Convolution (TAKEZAKI・SUGIYAMA)
― ― 4. Conclusion
The numerical results of the density function fp(x) is as
shown in Fig.1. On graphing the density function fp(x) for
each value, when p = 6,7, ･ ･ ･,11, these are plotted as the numbered curves in Fig.1. Since this is a partial sum of the spline function, it can be expected to approximate the function
fp(x). Although we stopped the calculation at p = 11 which
shows this partial sum of 2014 terms, the calculation for larger
p is possible if it is necessary.
Fig.1 Density functions fp(x) for p = 6,7,8,9,10,11
References
[1] S.O.Rice, " Stastitical properties of the response of a resonant circuit to a train of random pulses, " Bell Labs., 1957,unpublished.
[2] A.Huzii and H. Sugiyama, "Intersymbol interference of Markov pulse train," Electoron, Commun. Japan, Vol.53-A, pp.21-30, 1970.
[3] F.S.Hill and M.A.Blanco, "Random geometric series and intersymbol interference,"IEEE Trans.Inform.Theory,Vol.IT-19,pp.326-335,May 1973.
[4] J.Wintner,"Distribution function and the Riemannzeta function," Amer.J. Math.,38,pp.48-88, 1935.
[5] P.H.Wittke, W.S.Smith, and L.L.Campbell,"Infinite series of interference variables with Cantor-type distributions,"IEEE Trans.Inform.Theory, Vol.IT 34, pp.1428-1436,Nov. 1988. [6] H. Sugiyama and A.Huzii ,” Bernoulli distribution function”
IEICE Technical Report(Rep. IT93-126), March 1994. [7] H.Sugiyama and A.Huzii,"On the ditribution function of a
random power series with Bernoulli variables as coefficients, "IEEE Trans. Inform. Theory, Vol.IT 41, pp.2007-2008,Nov.1995.
[8] L . Ammeraal, PROGRAMS AND DATA STRUCTURES IN C., pp.77-91, Wiley,1992.
