ИРЭ им. В.А. Котельникова РАН English Войти Подать статью
Журнал радиоэлектроники Электронный научный журнал · eISSN 1684-1719
2019, № 1 · РАДИОТЕХНИКА

Перемежение в канальном кодировании: свойства, структура, специфика применения

А.Ю. Баринов1,2

1 Череповецкое высшее военное инженерное училище радиоэлектроники, Череповец, Россия
2 Cherepovets Higher Military Engineering School of Radio Electronics, Россия
Полный текст (PDF) DOI: 10.30898/1684-1719.2019.1.13 УДК 621.391 EDN TYAUVA

Аннотация

Перемежение является крайне важной процедурой в канальном кодировании для получения максимальной дистанции между кодовыми словами. В статье представлен обзор результатов исследований принципов перемежения с учетом особенностей помехоустойчивых кодов и требуемых условий использования. При этом особое внимание уделено исследованию S -случайного перемежителя. Предложены варианты технической реализации перемежителей. Рассмотрено применение перемежения для обеспечения защиты информации.

  • перемежение
  • перемежитель
  • псевдослучайный перемежитель
  • S-случайный перемежитель
  • свойства перемежителя
  • структура перемежителя
  • применение перемежения
  • помехоустойчивость
  • защита информации
  • interleaving
  • interleaver
  • pseudorandom interleaver
  • S-random interleaver
  • interleaver properties
  • interleaver structure
  • applications of interleaving
  • noise immunity
  • information security
Abstract (in English)

Interleaving in channel coding: properties, structure, applications

Interleaving is an extremely important procedure in channel coding where we look for the longest distance between codewords. Nowadays there are many kinds of interleavers and their design depends upon the component codes and the application. However, in most cases, theory of interleavers is examined in a general or abstract way that can be equivocated. In this paper, the author thoroughly examined interleavers from combination of mathematical and engineering standpoints. The basic properties of interleavers such as period, memory, latency, spreading factor and dispersion are presented. The proposed classification captures two parent classes of block and convolutional interleavers with division according to random, pseudorandom and deterministic generation process. Special attention is paid to S -random interleaver. Several schemes for efficient hardware realization of interleaving are presented. In addition, the graphical representation of the popular interleavers is depicted. The author considers the usage of interleavers for error protection. Whereas in a conventional serial concatenated code an interleaver is used merely to spread out burst errors, the interleaver in modern iteratively decodable codes plays a far more important role. In general, in modern codes, deterministic interleavers can perform equal or better than pseudorandom interleavers if the size of the interleaver is small, and pseudorandom interleavers perform better than deterministic interleavers when the size of the interleaver is medium or large. Nevertheless capacity-approaching performances for modern codes are achieved using pseudorandom interleavers with period of order several thousand bits. In conclusion, the author considers secondary usage of interleavers - for information security. Wireless telecom systems can be intercepted and monitored, as a result there are many technics of protection. A very high level of security may be obtained using combination of cryptography and steganography technics with channel coding. Enhanced security may be obtained using large pseudorandom interleavers in the channel coding. The evaluation of S -random interleavers diversity is also presented.

Для цитирования

Баринов А.Ю. Перемежение в канальном кодировании: свойства, структура, специфика применения // Журнал радиоэлектроники. – 2019. – № 1. https://doi.org/10.30898/1684-1719.2019.1.13

Литература

  1. Lin S., Costello D.J., Jr. Error control coding, 2nd ed. Pearson Prentice Hall, New Jersey, 2004, 1260 p.
  2. Costello D.J., Jr, Forney G.D., Jr. Channel coding: The road to channel capacity. Proc. IEEE, 2007, Vol. 95. No. 6, pp. 1150-1177.
  3. Andrews K., Heegard C., Kozen D. A theory of interleavers. Technical report TR97-1634, Department of Computer Science, Cornell University, 1997.
  4. Dolloff J., Kenz Z., Rische J., Rogers D.A., Smih L., Mosteig E. Algebraic interleavers in turbo codes. Applied Mathematical Sciences Summer Institute, Department of Mathematics & Statistics, California State Polytechnic University, Pomona 3801 W. Temple Ave. Pomona, California, 2006, 76 p.
  5. Johnson S.J. Iterative error correction. Turbo, low-density parity-check and repeat accumulate codes. Cambridge University Press, New York, 2010, 335 p.
  6. Helical interleaver [online]. Available at: https://www.mathworks.com/help/comm/ref/helicalinterleaver.html
  7. Bendetto S., Montorsi G. Unveiling turbo codes: Some results on parallel concatenated coding schemes. IEEE Trans. Inform. Theory, 1996, Vol. IT-42, pp. 409-428.
  8. Dolinar S., Divsalar D. Weight distributions for turbo codes using random and nonrandom permutations. 1995. TDA Progress Report 42-122, Jet Propulsion Laboratory, Pasadena, California, pp. 56-65.
  9. Popovski P., Kocarev L., Risreski A. Design of flexible-length S-random interleaver for turbo codes, IEEE Commun. Letter, 2004, Vol. 8, No. 7, pp. 461-463.
  10. Dinoi L., Bendetto S. Design of fast prunable S-random interleavers. IEEE Trans. Wireless Commun., 2005, Vol. 4, No. 5, pp. 1-9.
  11. Matrix Helical Scan Interleaver [online]. Available at: https://www.mathworks.com/help/comm/ref/matrixhelicalscaninterleaver.html
  12. Heegard C., Wicker S.B. Turbo Coding. Kluwer Academic Publishers, Boston, 1999, pp. 54-55.
  13. Takeshita O.Y., Costello D.J., Jr. New classes of algebraic interleavers for turbo-codes. Proc. 1998 IEEE ISIT, Boston, 1998, pp. 419.
  14. Sun J., Takeshita O.Y. Interleavers for turbo codes using permutation polynomial over integer rings. IEEE Trans. Inform. Theory, 2005, Vol. 51, No 1, pp. 101-119.
  15. Elias P. Error-free coding. IRE Trans. Inform. Theory, 1954, Vol. IT-4, pp. 29-37.
  16. Forney G.D., Jr. Concatenated Codes. MIT Press, Cambridge, 1966.
  17. Berrou C., Glavieux A., Thitimasjshima P. Near Shannon limit error-correcting coding and decoding: Turbo codes. Proc. IEEE Int. Conf. on Communications, Geneva, Switzerland, May 1993, pp. 1064-1070.
  18. Pyndiah R.M. Near-optimum decoding of product codes: block turbo codes. IEEE Transactions on Communications, 1998, Vol. 46, No 8, pp. 1003-1010.
  19. Gallager R.G. Low-density parity-check codes. IRE Trans. Inform. Theory, 1962, Vol. IT-8, pp. 21-28.
  20. Divsalar D., Jin H., McEliece R.G. Coding theorems for turbo-like codes, Proc. 1998 Allerton Conf. Allerton, IL, September 1998, pp. 201-210.
  21. Кудряшов Б.Д. Основы теории кодирования. - СПб.: БХВ-Петербург, 2016. - 400 c.
  22. Голиков А.М. Модуляция, кодирование и моделирование в телекоммуникационных системах. Теория и практика. - Томск: Томск. гос. ун-т систем упр. и радиоэлектроники, 2016. - 516 с.
  23. Berrou C., Glavieux A. Near optimum error correcting coding and decoding, IEEE Trans. Comm., 1996, Vol. 44, No. 10, pp. 1261-1271.
  24. Vucetic B., Yuan J. Turbo codes: principles and applications, Kluwer Academic, Norwell, MA, 2000, 312 p.
  25. Abbasfar A., Divsalar D., Kung Y. Accumulate-repeat accumulate codes, Proc. IEEE Global Telecommunications Conference (GLOBECOM 2004), Dallas, TX, December 2004, pp. 509-513.
  26. Halford T.R., Bayram M., Kose C., Chugg K.M., Polydoros A. The F-LDPC family: High-performance flexible modern codes for flexible radio, in Proc. ISSSTA 2008, Bologna, Italy, September 2008, pp. 376-380.
  27. Jin H., Khandekar A., McEliece R. Irregular repeat-accumulate codes, In Proc. 2nd Int. Symp. Turbo codes and related topics, Brest, France, September 2000, pp. 1-8.
  28. Forney G.D., Jr., Codes on graphs: Normal realizations, IEEE Trans. Inform. Theory, 2001, Vol. IT-13, pp. 520-548.
  29. Moreira J.C., Farrell P.G. Essentials of error control coding, John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, England, 2006, 361 p.
  30. Скляр Б. Цифровая связь. Теоретические основы и практическое применение, 2-е изд. / Б. Скляр; Пер. с англ. Е.Г. Грозы [и др.]; под редакцией А.В. Назаренко - М.: Вильямс, 2003. - 1104 с.
  31. Canteaut A., Filiol E. Ciphertext only reconstruction of stream ciphers based on combination generators, Berlin, Springer, 2001, 16 p.
  32. Cluzeau M. Reconstruction of a linear scrambler, IEEE Trans. on Computers, 2007, Vol. 56, No. 8, pp. 1283-1293.
  33. Кривоногов А.С., Кривоногова Е.О. Алгоритм идентификации вида скремблирования бинарных данных // Известия Вузов России. Радиоэлектроника. 2017. № 6. С. 10-14.
  34. Sicot G., Houcke S. Blind detection of interleaver parameters. Proc. IEEE ICASSP, March 2005, pp. 829-832.
  35. Cluzeau M, Finiasz M, Tillich J, Methods for the reconstruction of Parallel Turbo Codes. in Proc. IEEE Int. Symp. Information Theory (ISIT '10), Austin, Texas, USA, June 2010, pp. 2008-2012.
  36. Tillich J., Tixier A., Sendrier N., Recovering the interleaver of an unknown Turbo-Code, in Proc. IEEE Int. Symp. Information Theory (ISIT '14), Honolulu, Hawaii, USA, 2014, pp. 2784-2788.
  37. Баринов А.Ю. Методы анализа турбоподобных кодов с учетом идентификации их компонентных перемежителей // Наукоемкие технологии. 2016. № 12. C. 4-11.
  38. Баринов А.Ю., Асеев А.Ю. Модифицированная математическая модель системы генерирования перемеженной дискретной последовательности турбоподобного кода // Вестник Череповецкого государственного университета. 2017. №6 (81). С. 9-18. DOI 10.23859/1994-0637-2017-6-81-1
  39. Баринов А.Ю. Идентификация перемежителей турбокодов на основе их полиномиального и матричного представления // Информация и Космос. 2018. № 2. C. 61-66.