Inspection of the Output of a Convolution and Deconvolution Process from the Leading Digit Point of View—Benford’s Law

1. Introduction

We consider a blind deconvolution problem in which we observe the output of an unknown, possibly nonminimum phase, linear system (single-input-single-output (SISO) finite impulse response (FIR) system) from which we want to recover its input (source) using an adjustable linear filter (equalizer). During transmission, a source signal undergoes a convolutive distortion between its symbols and the channel impulse response. This distortion is referred to as ISI [1] [2] [3] . It is well known that ISI is a limiting factor in many communication environments where it causes an irreducible degradation of the bit error rate thus imposing an upper limit on the data symbol rate [1] [4] . In order to overcome the ISI problem, a blind adaptive equalizer can be implemented in those systems [2] - [26] . But, since no training symbols are used in the deconvolution process and the channel coefficients are unknown to the receiver, no indication can be made (via the ISI or MSE expressions) during the deconvolution process whether the blind adaptive equalizer succeeded to remove the heavy ISI from the transmitted symbols or not. Such an information can be very useful to those systems involving the variable step-size parameter technique to get on one hand a fast removal of the heavy ISI by applying initially a relative high valued step-size parameter and then continuing with another step-size parameter which is lower compared to the first one in order to achieve on the other hand a very low residual ISI at the latter stages of the deconvolution process [27] - [30] .

According to [31] , Benfords law (also known as the first-digit law) defines a peculiar distribution of the leading digits of a set of numbers. The behavior is logarithmic, with the leading digit 1 reflecting largest probability of occurrence and the remaining ones showing decreasing probabilities of appearance following a logarithmic trend. According to [31] , Benfords law has been widely proposed as a discriminating tool for naturally-shaped datasets [32] and even employed [33] or criticized [34] as a somewhat reliable diagnostic tool to detect a large variety of frauds. In [31] , Benfords law was evaluated as a discriminator for audio signals. In particular it was employed to detect differences between natural and artificially created chords and real music.

In the communication field, the transmitted symbols may belong to a squared constellation input such as the 16QAM or to a PAM constellation where the transmitted symbols are statistically independent and have the same probability to appear for transmission. Thus, the recovered symbols should also appear approximately with equal probability. Up to now, the output of a convolution process such as the output of a channel was mainly investigated from the ISI point of view. In this paper, the output of a convolution and deconvolution process is inspected from the leading digit point of view. Simulation results will indicate that for the 4PAM and 16QAM constellation input, the number 1 is the leading digit at the output of a convolution and deconvolution process respectively as long as heavy ISI exists. However, this leading digit does not follow exactly Benford’s Law but follows approximately the leading digit (digit 1) of a Gaussian process for independent identically distributed input symbols and a channel with many coefficients.

The paper is organized as follows: After having described the system under consideration in Section 2, the inspection of the output of a convolution and deconvolution process from the leading digit point of view is given via simulation results in Section 3. Section 4 is our conclusion.

2. System Description

The system under consideration is illustrated in Figure 1, where we make the following assumptions:

1) The input sequence belongs to a 16QAM input constellation (a modulation using ± {1, 3} levels for in-phase and quadrature components) or a 4PAM case (a modulation using ± {1, 3} levels for the symbols) with variance where and are the real and imaginary parts of respectively. The input symbols are independent and identically distributed.

2) The unknown channel is a possibly nonminimum phase linear time-in- variant filter in which the transfer function has no “deep zeros”, namely, the zeros lie sufficiently far from the unit circle.

3) The equalizer is a tap-delay line.

4) The noise is an additive Gaussian white noise with zero mean and variance where is the expectation operator and is the conju- gate operation on.

The transmitted sequence is sent via the channel where it is also cor- rupted with noise. Thus, the equalizer’s input sequence may be written as:

(1)

where “” denotes the convolution operation. The equalized output sequence is defined by:

(2)

where is the convolutional noise (convolutional error) due to non-ideal equalizer’s coefficients () and. Next, we turn to the mathe- matical definition of the ISI expression:

(3)

where is the component of, given by, having the maximal absolute value. Now, we turn to the adaptation mechanism of the equalizer’s coefficients which is based in this paper on Godard’s method [5] (a cost function approach):

Figure 1. Block diagram of a baseband communication system.

(4)

where is the step-size parameter, is the absolute value of,

and N is the equalizer’s tap length. Please note that we could use here for the blind adaptive deconvolution method any other cost function approach like the one given in [6] [9] [10] [12] [13] [20] or [24] for instance as well as just using the Bayesian technique as was done in [4] [17] [21] [22] and [26] . Next, we introduce Benford’s Law. According to [31] , the probability value of the d-th digit is computed as follows:

(5)

where d is the digit number.

3. The Output of a Convolution and Deconvolution Process from the Leading Digit Point of View

In this section we first start to inspect the output of the convolution process from the leading digit point of view for the noiseless case. After that, we turn to inspect the output of the deconvolution process considering also the noisy situation.

In the following we use the 4PAM constellation input with three different channel cases having real valued coefficients:

Case I: Rayleigh fading channel with variance equal to 0.2.

Case II: Gaussian channel with zero mean and variance equal to 1.

Case III: A channel where the coefficients are uniformly distributed within.

Figures 2-8 show the averaged value for the leading-digit distribution for 9000 symbols

Figure 2. The leading-digit distribution for 9000 symbols (4PAM constellation) sent via a Rayleigh channel compared to Benford’s law. The channel length was set to 13. The averaged results were obtained in 100 Monte Carlo trials for the noiseless case.

Figure 3. The leading-digit distribution for 9000 symbols (4PAM constellation) sent via a Rayleigh channel compared to Benford’s law. The channel length was set to 23. The averaged results were obtained in 100 Monte Carlo trials for the noiseless case.

Figure 4. The leading-digit distribution for 9000 symbols (4PAM constellation) sent via a Rayleigh channel compared to Benford’s law. The channel length was set to 33. The averaged results were obtained in 100 Monte Carlo trials for the noiseless case.

Figure 5. The leading-digit distribution for 9000 symbols (4PAM constellation) sent via a Rayleigh channel compared to Benford’s law. The channel length was set to 53. The averaged results were obtained in 100 Monte Carlo trials for the noiseless case.

Figure 6. The leading-digit distribution for 9000 symbols (4PAM constellation) sent via a gaussian channel compared to Benford’s law. The channel length was set to 13. The averaged results were obtained in 100 Monte Carlo trials for the noiseless case.

Figure 7. The leading-digit distribution for 9000 symbols (4PAM constellation) sent via the channel compared to Benford’s law. The channel’s coefficients were uniformly distributed within. The channel length was set to 13. The averaged results were obtained in 100 Monte Carlo trials for the noiseless case.

Figure 8. The leading-digit distribution for 9000 symbols (4PAM constellation) sent via the channel compared to Benford’s law. The channel’s coefficients were uniformly distributed within. The channel length was set to 53. The averaged results were obtained in 100 Monte Carlo trials for the noiseless case.

Figure 9. The leading-digit distribution for 9000 numbers belonging to a gaussian distribution with zero mean and variance 1 compared to Benford’s law. The averaged results were obtained in 100 Monte Carlo trials.

Figure 10. Probability of occurrence of the number 1 minus the probability of occurrence of the number “i” (where) for each trial out of the 100 Monte Carlo trials. The results were obtained by sending 9000 symbols (4PAM constellation) via channel case I where the channel length was set to 13.

Figure 11. Probability of occurrence of the number 1 minus the probability of occurrence of the number “i” (where) for each trial out of the 100 Monte Carlo trials. The results were obtained by sending 9000 symbols (4PAM constellation) via channel case I where the channel length was set to 23.

Figure 12. Probability of occurrence of the number 1 minus the probability of occurrence of the number “i” (where) for each trial out of the 100 Monte Carlo trials. The results were obtained by sending 9000 symbols (4PAM constellation) via channel case I where the channel length was set to 33.

Figure 13. Probability of occurrence of the number 1 minus the probability of occurrence of the number “i” (where) for each trial out of the 100 Monte Carlo trials. The results were obtained by sending 9000 symbols (4PAM constellation) via channel case I where the channel length was set to 53.

Figure 14. Probability of occurrence of the number 1 minus the probability of occurrence of the number “i” (where) for each trial out of the 100 Monte Carlo trials. The results were obtained by sending 9000 symbols (4PAM constellation) via channel II where the channel length was set to 13.

Figure 15. Probability of occurrence of the number 1 minus the probability of occurrence of the number “i” (where) for each trial out of the 100 Monte Carlo trials. The results were obtained by sending 9000 symbols (4PAM constellation) via channel case III where the channel length was set to 13.

Figure 16. Probability of occurrence of the number 1 minus the probability of occurrence of the number “i” (where) for each trial out of the 100 Monte Carlo trials. The results were obtained by sending 9000 symbols (4PAM constellation) via channel case III where the channel length was set to 53.

number 1 minus the probability of occurrence of the number “i” (where

) is higher than zero for each trial out of the 100 Monte Carlo trials. Thus, according to Figures 10-16, the leading digit is the number 1.

Now, we turn to the deconvolution case where the equalized output is of our interest. 9000 symbols belonging to a 16QAM input constellation were sent via the channel used in [20] :

.

Usually, the equalizer’s coefficients are updated constantly. However, in order to see the behaviour of the leading digit at the equalized output during the deconvolution process, the updating mechanism of the equalizer’s coefficients was stopped at several places during the deconvolution process. Namely, the equalizer’s coefficients were updated as long as we have not reached the desired iteration number. For example, if the desired iteration number was set to 10, then the equalizer’s coefficients were not updated anymore after 10 iterations. Thus, the residual ISI level at the equalizer’s output remained fixed. Figures 17-20 show the averaged value for the leading-digit distribution at the equalized output for SNR of 30 dB compared with Benford’s law. Based on the obtained results for the convolution case described earlier in this section, it was quite expected to get the number 1 as the leading digit at the equalized output at the early stages of the deconvolution process (Figure 17, Figure 18). In addition, as it was for the convolution case, the leading digit (number 1) at the equalized output does

Figure 17. The leading-digit distribution at the equalized output compared to Benford’s law. The channel length as well as the equalizer’s tap length were set to 13. The step-size parameter was set to 0.00008. The averaged results were obtained in 100 Monte Carlo trials for. After 10 iterations the averaged residual ISI reached −3.75 dB and at that level of the residual ISI the equalizer’s coefficients were not updated anymore.

Figure 18. The leading-digit distribution at the equalized output compared to Benford’s law. The channel length as well as the equalizer’s tap length were set to 13. The step-size parameter was set to 0.00008. The averaged results were obtained in 100 Monte Carlo trials for. The averaged residual ISI was −7.5 dB after 200 iterations.

Figure 19. The leading-digit distribution at the equalized output compared to Benford’s law. The channel length as well as the equalizer’s tap length were set to 13. The step-size parameter was set to 0.00008. The averaged results were obtained in 100 Monte Carlo trials for. The averaged residual ISI was −14 dB after 500 iterations.

Figure 20. The leading-digit distribution at the equalized output compared to Benford’s law. The channel length as well as the equalizer’s tap length were set to 13. The step-size parameter was set to 0.00008. The averaged results were obtained in 100 Monte Carlo trials for. The averaged residual ISI was −17 dB after 800 iterations.

not follow Benford’s law. According to Figure 19 and Figure 20 the number 1 is no more the leading digit at the equalized output. Thus, this may indicate that most of the ISI is already removed by the equalizer which is confirmed in our case with Figure 21 and Figure 22. Figures 23-26 show the probability of occurrence of the number 1

Figure 21. The real part of the equalized output for. The channel length as well as the equalizer’s tap length were set to 13. The step-size parameter was set to 0.00008. The averaged residual ISI was −14 dB after 500 iterations.

Figure 22. The real part of the equalized output for. The channel length as well as the equalizer’s tap length were set to 13. The step-size parameter was set to 0.00008. The averaged residual ISI was −17 dB after 800 iterations.

Figure 23. Probability of occurrence of the number 1 minus the probability of occurrence of the number “i” (where) for each trial out of the 100 Monte Carlo trials obtained at the equalized output for. The channel length as well as the equalizer’s tap length were set to 13. The step-size parameter was set to 0.00008. The averaged residual ISI was −3.75 dB after 10 iterations.

Figure 24. Probability of occurrence of the number 1 minus the probability of occurrence of the number “i” (where) for each trial out of the 100 Monte Carlo trials obtained at the equalized output for. The channel length as well as the equalizer’s tap length were set to 13. The step-size parameter was set to 0.00008. The averaged residual ISI was −7.5 dB after 200 iterations.

Figure 25. Probability of occurrence of the number 1 minus the probability of occurrence of the number “i” (where) for each trial out of the 100 Monte Carlo trials obtained at the equalized output for. The channel length as well as the equalizer’s tap length were set to 13. The step-size parameter was set to 0.00008. The averaged residual ISI was −14 dB after 500 iterations.

Figure 26. Probability of occurrence of the number 1 minus the probability of occurrence of the number “i” (where) for each trial out of the 100 Monte Carlo trials obtained at the equalized output for. The channel length as well as the equalizer’s tap length were set to 13. The step-size parameter was set to 0.00008. The averaged residual ISI was −17 dB after 800 iterations.

minus the probability of occurrence of the number “i” (where) for each trial out of the 100 Monte Carlo trials valid at the equalized output for SNR of 30 dB. Since the transmitted symbols were sent statistically independent with the same probability to appear, the recovered symbols should also appear approximately with equal probability. Indeed, according to Figures 23-26, the probability of occurrence of the number 1 minus the probability of occurrence of the number 3 is approximately zero only at the latter stages of the deconvolution process (Figure 25, Figure 26) while this is not the case at the earlier stages of the deconvolution process (Figure 23, Figure 24). Please note that according to Figure 24, the number 1 was not the leading number for the entire 100 Monte Carlo trials. This outcome can be explained by the fact that the residual ISI was probably much lower than the averaged residual ISI of −7.5 dB. Thus, the system was closer to the symbol recovery state. Next, we turn to the case. Figures 27-29 show the averaged value for the leading-digit distribution at the equalized output for SNR of 20 dB compared with Benford’s law. As it was for the case of, the number 1 is the leading digit at the equalized output at the early stages of the deconvolution process (Figure 27). According to Figure 28 and Figure 29 the number 1 is no more the leading digit at the equalized output. Thus, this may indicate that most of the ISI is already removed by the equalizer which is confirmed in our case with Figure 30 and Figure 31. In addition, the leading digit (number 1) does not follow Benford’s law (Figure 27). Figures 32-34 show the probability of occurrence of the number 1 minus the probability of occurrence of the number “i” (where

) for each trial out of the 100 Monte Carlo trials valid at the equalized

Figure 27. The leading-digit distribution at the equalized output compared to Benford’s law. The channel length as well as the equalizer’s tap length were set to 13. The step-size parameter was set to 0.00008. The averaged results were obtained in 100 Monte Carlo trials for. The averaged residual ISI was −3.75 dB after 10 iterations.

Figure 28. The leading-digit distribution at the equalized output compared to Benford’s law. The channel length as well as the equalizer’s tap length were set to 13. The step-size parameter was set to 0.00008. The averaged results were obtained in 100 Monte Carlo trials for. The averaged residual ISI was −11.5 dB after 400 iterations.

Figure 29. The leading-digit distribution at the equalized output compared to Benford’s law. The channel length as well as the equalizer’s tap length were set to 13. The step-size parameter was set to 0.00008. The averaged results were obtained in 100 Monte Carlo trials for. The averaged residual ISI was −16.5 dB after 800 iterations.

Figure 30. The real part of the equalized output for. The channel length as well as the equalizer’s tap length were set to 13. The step-size parameter was set to 0.00008. The averaged residual ISI was −11.5 dB after 400 iterations.

Figure 31. The real part of the equalized output for. The channel length as well as the equalizer’s tap length were set to 13. The step-size parameter was set to 0.00008. The averaged residual ISI was −16.5 dB after 800 iterations.

Figure 32. Probability of occurrence of the number 1 minus the probability of occurrence of the number “i” (where) for each trial out of the 100 Monte Carlo trials obtained at the equalized output for. The channel length as well as the equalizer’s tap length were set to 13. The step-size parameter was set to 0.00008. The averaged residual ISI was −3.75 dB after 10 iterations.

Figure 33. Probability of occurrence of the number 1 minus the probability of occurrence of the number “i” (where) for each trial out of the 100 Monte Carlo trials obtained at the equalized output for. The channel length as well as the equalizer’s tap length were set to 13. The step-size parameter was set to 0.00008. The averaged residual ISI was −11.5 dB after 400 iterations.

Figure 34. Probability of occurrence of the number 1 minus the probability of occurrence of the number “i” (where) for each trial out of the 100 Monte Carlo trials obtained at the equalized output for. The channel length as well as the equalizer’s tap length were set to 13. The step-size parameter was set to 0.00008. The averaged residual ISI was −16.5 dB after 800 iterations.

output for SNR of 20 dB. According to Figures 32-34, the probability of occurrence of the number 1 minus the probability of occurrence of the number 3 is approximately zero only at the latter stages of the deconvolution process (Figure 34) while this is not the case at the earlier stages of the deconvolution process (Figure 32).

4. Conclusion

In this paper, we have shown via simulation results that the number 1 is the leading digit at the output of a convolution and deconvolution process for a 4PAM and 16QAM input constellation respectively, as long as heavy ISI exists. In addition, simulation results have shown that the behaviour of this leading digit does not follow exactly Benford’s Law but follows approximately the leading digit (digit 1) of a Gaussian process for independent identically distributed input symbols and a channel with many coefficients.

Acknowledgements

We thank the Editor and the referee for their comments.

Abbreviations

ISI: Intersymbol Interference

SNR: Signal to Noise Ratio

SISO: Single Input Single Output

FIR: Finite Impulse Response

PAM: Pulse Amplitude Modulation

Submit or recommend next manuscript to SCIRP and we will provide best service for you:

A wide selection of journals (inclusive of 9 subjects, more than 200 journals)

Providing 24-hour high-quality service

User-friendly online submission system

Fair and swift peer-review system

Display of the result of downloads and visits, as well as the number of cited articles

Maximum dissemination of your research work

Or contact jsip@scirp.org

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

Pinchas, M. (2016) Inspection of the Output of a Convolution and Deconvolution Process from the Leading Digit Point of View—Benford’s Law. Journal of Signal and Information Processing, 7, 227-251. doi: 10.4236/jsip.2016.74020.