"JOURNAL OF RADIO ELECTRONICS" (Zhurnal Radioelektroniki ISSN 1684-1719, N 1, 2019

contents of issue      DOI  10.30898/1684-1719.2019.1.13    full text in Russian (pdf)  

Interleaving in channel coding: properties, structure, applications

 

A. Y. Barinov

Cherepovets Higher Military Engineering School of Radio Electronics,

Sovetskiy 126, Cherepovets 162622, Russia

 

The paper is received on December 17, 2018, after correction on December 24, 2018

 

Abstract. 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.

Key words: interleaving, interleaver, pseudorandom interleaver, S-random interleaver, interleaver properties, interleaver structure, applications of interleaving, noise immunity, information security

References

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. 10641070.

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. 201210.

21.  Kudryashov B.D. Osnovi teorii kodirovaniya [Fundamentals of coding theory]. Saint-Petersburg, BHV-Peterburg Publ., 2016. 400 p. (In Russian)

22.  Golikov A.M. Modulyatsiya, kodirovanie i modelirovanie v telekommunikatsionnih sistemah. Teoriya i praktika [Modulation, coding and modeling in telecom systems. Theory and practice]. Tomsk, Tomsk State University of Control Systems and Radio Electronics. 2016. 516 p. (In Russian)

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. 509513.

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. 376380.

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. 18.

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.  Sklar B. Digital Communications. Fundamentals and Applications. 2nd ed. 2001, Prentice-Hall, Upper Saddle River, New Jersey, 2001, 1079 p.

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.  Krivonogov A.S., Krivonogova E.O. Linear scrambler identification. Izvestiya Vyshikh Uchebnikh Zavedenii Rossii. Radioelectronika [Journal of the Russian Universities. Radioelectronics]. 2017, No. 6, pp. 10-14. (In Russian)

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. 20082012.

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. 27842788.

37.  Barinov A.Y. Methods of turbo-like codes analysis in view of their component interleavers identification. Naukoemkie tehnologii [Science Intensive Technologies], 2016, No. 12, pp. 4 11. (In Russian)

38.  Barinov A.Y., Aseev A.Y. Modified mathematical model of system generating turbo-like interleaved discrete code sequence. Vestnik Cherepovetskogo Gosudarstvennogo Universiteta [Bulletin of the Cherepovets State University], 2017, No. 6 (81), pp. 918. DOI 10.23859/1994-0637-2017-6-81-1. (In Russian)

39.  Barinov A.Y. Identification of turbo code interleavers, depending on their polynomial and matrix representation. Informatsiya i Kosmos [Information and Space], 2018, No. 2, pp. 61-66. (In Russian)

 

For citation:

A. Y. Barinov. Interleaving in channel coding: properties, structure, applications. Zhurnal Radioelektroniki - Journal of Radio Electronics. 2019. No. 1. Available at http://jre.cplire.ru/jre/jan19/13/text.pdf

DOI  10.30898/1684-1719.2019.1.13