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