O.V. Ershova – Programmer, Supercomputers and Neurocomputers Research Center (Taganrog)
E.V. Kirichenko – Research Scientist, Supercomputers and Neurocomputers Research Center (Taganrog)
M.S. Kocherga – Leading Designer, Supercomputers and Neurocomputers Research Center (Taganrog)
E.A. Semernikov – Ph. D. (Eng.), Head of Department of Digital Signal Processing, Supercomputers and Neurocomputers Research Center (Taganrog)
In signal detection systems to evaluate the threshold robust analogs of the mean value and dispersion are frequently used. In this case, the value of the threshold can be determined through the value of the q quantile. It is the smallest sample value of the ordered data sequence. The q-th portion of all values of the sequence lies below that value.
Despite the obvious advantage of using quantiles in calculating the threshold, the very procedure of quantile calculating is rather la-borious. A large number of sorting algorithms are known. They can be compared according to different criteria: stability, execution speed, memory efficiency, etc. For digital data processing methods, in most cases, the main efficiency criterion is the possibility of using them in real-time measuring systems. This criterion is met by the algorithm of sorting by counting. A device for accurately determining quantiles of an array of random numbers can be created based on this algorithm. The advantage of this scheme is one pass of the array through the circuit. The disadvantage is a large amount of memory requiring for accumulating partial sums that is equal to the maximum possible number of the range of values that can be taken by the elements of the array.
In the article, in order to reduce the amount of memory for partial sums and the number of calculations in finding quantiles, it is pro-posed to divide the entire input range into non-uniform intervals, using the non-uniform quantization approach. In this case, the quantization step (in our case, the partition interval) has a minimum value in the lower part of the range and increases with the level of the input data. This corresponds to an intuitive understanding of the statistical characteristics of noise.
Based on the requirements of resource efficiency, the simplicity of the hardware implementation and the obtainment of a relative computational error of no more than the given one, a new method of dividing the range of possible amplitude values into a system of non-uniform intervals was developed and tested.
An algorithm for determining quantiles values of the noise process with a given relative accuracy in radar signals detection problems based on this method provides the calculation of quantiles in one data pass. It makes possible to use this algorithm in pipeline processing devices.
The algorithm requires essentially less memory for storing partial sums than the sorting by counting algorithm. The method of ad-dressing partial sums does not contain comparison operations, but uses a binary representation of the current input sample instead. The algorithm allows to control the relative accuracy of calculating quantiles no more than a given value. Parameters of the algorithm can be adapted depending on the required accuracy of calculating quantiles, which minimizes hardware costs.
The algorithm proposed in this article showed a good result and can be used both in general-purpose computers and in specialized hardware circuits based on FPGAs.
- Kuz’min S.Z. Czifrovaya radiolokacziya. Vvedenie v teoriyu. Kiev: Izd-vo KViCz. 2000. 428 s.
- X’yuber P. Robastnost’ v statistike. M.: Mir. 1984. 304 s.
- Rud’ko I.M. Primenenie poryadkovy’x statistik v zadachax obnaruzheniya / Upravlenie bol’shimi sistemami. Vy’pusk 37. M.: IPU RAN. 2012. S. 63−83.
- Korn G., Korn T. Spravochnik po matematike. M.: Nauka. 1973. 832 s.
- Pat. RU 2253147 C1, G 06 F 17/18. Ustrojstvo dlya opredeleniya xarakteristik sluchajnogo proczessa / Tolparev R.G., Gorshenev G.A., Shishkin S.Yu. Zayavka 12.11.2003. Opublikovano 27.05.2005.
- Pat. № US 8,000,929 B2. Int. Cl. G 06 F 17/18. Hoeflin. Sequential fixed-point quantile estimation / Yuri Bakshi, David Arthur. Filled: Aug. 28, 2008. Prior Publication Data May 28. 2009.
- Pat. № US 9268796 B2. Int. Cl. G 06 F 17/30. Systems and methods for quantile estimation in a distributed data system / Scott Pope, Georges H. Gulrguis, Oliver Schabenberger. Filled: May 29. 2012. Prior Publication Data Dec. 5. 2013.
- Pat. № US 2010/0292995 A1. Int. Cl. G 06 Q 99/00. Method and apparatus for incremental quantile estimation. Tian Bu, Jin Cao, Li Li. Filled: May 18, 2009. Prior Publication Data Dec. 5. 2013.
- Join C. Liechty, James P. McDermott, Dennis K.J. Lin. Single-pass low-storage arbitrary probalistic location estimation for massive data sets. Statistics and Computing. 2003. № 13. P. 91−100.
- Knut D. Iskusstvo programmirovaniya dlya E’VM. T. 3. Sortirovka i poisk. M.: Mir. 1978. 844 s.
- Kuz’min I.V., Kedrus V.A. Osnovy’ teorii informaczii i kodirovaniya. Kiev. Vishha shkola. 1986. 238 s.
- Sergienko A.B. Czifrovaya obrabotka signalov. Piter. 2002. 382 s.
- Berlin A.N. Okonechny’e ustrojstva i linii abonentskogo uchastka informaczionnoj seti. M.: Intuit. 2016. 395 s.