Журнал

About Editorial Board Information for authors and reviewers Publication ethics Contacts User Account: send / review a manuscript
Archive
Volume 21, 2024
Number 1
Volume 20, 2023
Number 1 Number 2 Number 3 Number 4 Number 5 Number 6
Volume 19, 2022
Number 1 Number 2 Number 3 Number 4 Number 5 Number 6
Volume 18, 2021
Number 1 Number 2 Number 3 Number 4 Number 5 Number 6
Volume 17, 2020
Number 1 Number 2 Number 3 Number 4 Number 5 Number 6 Number 7
Volume 16, 2019
Number 1 Number 2 Number 3 Number 4 Number 5 Number 6
Volume 15, 2018
Number 1 Number 2 Number 3 Number 4 Number 5 Number 6 Number 7
Volume 14, 2017
Number 1 Number 2 Number 3 Number 4 Number 5 Number 6 Number 7
Volume 13, 2016
Number 1 Number 2 Number 3 Number 4 Number 5 Number 6
Volume 12, 2015
Number 1 Number 2 Number 3 Number 4 Number 5 Number 6
Volume 11, 2014
Number 1 Number 2 Number 3 Number 4
Volume 10, 2013
Number 1 Number 2 Number 3 Number 4
Volume 9, 2012
Number 1 Number 2 Number 3 Number 4 Number 5
Volume 8, 2011
Number 1 Number 2 Number 3 Number 4
Volume 7, 2010
Number 1 Number 2 Number 3 Number 4
Issue 6, 2009
Volume 1 Volume 2
Issue 5, 2008
Volume 1 Volume 2
Issue 4, 2007
Volume 1 Volume 2
Issue 3, 2006
Volume 1 Volume 2
Issue 2, 2005
Volume 1 Volume 2
Issue 1, 2004
Volume 1
Search
Find:
русский
ISSN 2070-7401 (Print), ISSN 2411-0280 (Online)
Sovremennye problemy distantsionnogo zondirovaniya Zemli iz kosmosa
CURRENT PROBLEMS IN REMOTE SENSING OF THE EARTH FROM SPACE

  

Sovremennye problemy distantsionnogo zondirovaniya Zemli iz kosmosa, 2020, Vol. 17, No. 4, pp. 9-26

Overview of polar codes problems from Optimization Error Correction Coding Theory technologies points of view

ARTICLE RETRACTED BY THE EDITORS 19.07.2021
N.A. Kuznetsov 1 , V.V. Zolotarev 2 , G.V. Ovechkin 3 , R.R. Nazirov 2 , D.Zh. Satibaldina 4 , E.D. Omirbayev 4 
1 Kotelnikov Institute of Radioengineering and Electronics RAS, Moscow, Russia
2 Space Research Institute RAS, Moscow, Russia
3 Utkin Ryazan State Radio Engineering University, Ryazan, Russia
4 Gumilyov Eurasian National University, Astana, Republic of Kazakhstan
Accepted: 29.06.2020
DOI: 10.21046/2070-7401-2020-17-4-9-26
The general situation in the applied issues of coding theory is considered. The main problems in the field of decoding of error-correction codes are stated. The main attention in addition to error-correcting performance is paid to decoding complexity. The latest results in the field of decoding algorithms for polar codes (PC) are presented, as well as the main problems of their development. The application results of Optimization Theory (OT) and extremely limited materials available for PC are compared. The results for low density parity check (LDPC) codes are briefly mentioned. The results of performance comparison for PC and block version of Viterbi decoder (BVA) for short codes are presented. Also comparison of possibilities for PC and MTD algorithms, including using concatenation, was fulfilled. The main directions for the development and improvement of characteristics of OT algorithms are suggested. Based on the results of comparison, it has been concluded that there is an unconditional leadership of OT and no need to use PC and a number of other codes anywhere at all due to inevitably weak capabilities and a large list of shortcomings of decoders of these directions and methods of their development in research for new satellite and space communication projects, including remote sensing of Earth systems.
Keywords: Shannon boundary, channel capacity, algorithm complexity, polar codes, list decoding, optimal decoding, Optimization Theory, block viterbi algorithm, Reed – Solomon codes, low density parity check and turbo codes, multithreshold decoders, parallel concatenation, divergent principle, direct control metric decoders
Full text

References:

  1. Afanas’ev V. B., Davydov A. A., Zigangirov D. K., Otsenka doli stiranii, ispravlyaemykh lineinymi kodami (Estimation for part of erasures recovered with linear codes), Informatsionnye protsessy, 2016, Vol. 16, No. 4, pp. 352–404.
  2. Zigangirov D. K., Zigangirov K. Sh., Dekodirovanie nizkoplotnostnykh kodov s proverochnymi matritsami, sostavlennymi iz perestanovochnykh matrits, pri peredache po kanalu so stiraniyami (Decoding of low density codes with parity check matrixes consisting of permutation matrixes for erasure channels), Problemy peredachi informatsii, 2006, Vol. 42, pp. 44–52.
  3. Zolotarev V. V., Mnogoporogovoe dekodirovanie v nedvoichnykh kanalakh (Multithreshold decoding over non-binary channels), Voprosy radioelektroniki, Ser. EVT, 1984, Vol. 12.
  4. Zolotarev V. V., Teoriya i algoritmy mnogoporogovogo dekodirovaniya (Theory and algorithms for multithreshold decoding), Moscow: Goryachaya liniya — Telekom, 2006, 266 p.
  5. Zolotarev V. V., Teoriya kodirovaniya kak zadacha poiska global’nogo ekstremuma (Optimizatsionnaya Teoriya pomekhoustoichivogo kodirovaniya — novaya “kvantovaya mekhanika” teorii informatsii) (Coding Theory as a Global Extremum Search Task (Optimization Theory of error-correcting coding — a new “quantum mechanics” of information theory)), Moscow: Goryachaya liniya — Telekom, 2018, 222 p.
  6. Zolotarev V. V., Ovechkin G. V., Pomekhoustoichivoe kodirovanie. Metody i algoritmy (Error-correcting coding. Methods and algorithms), Moscow: Goryachaya liniya — Telekom, 2004, 126 p.
  7. Zolotarev V. V., Ovechkin G. V., Effektivnoe mnogoporogovoe dekodirovanie nedvoichnykh kodov (Effective multithreshold decoding for non-binary codes), Radiotekhnika i elektronika, 2010, Vol. 55, No. 3, pp. 324–329.
  8. Zolotarev V. V., Ovechkin G. V., Primenenie mnogoporogovykh metodov dekodirovaniya pomekhoustoichivykh kodov v vysokoskorostnykh sistemakh peredachi dannykh (Application of multuthreshold decoders for error-correcting codes in high-speed digital communications), Elektrosvyaz’, 2014, No. 12, pp. 10–14.
  9. Zolotarev V. V., Ovechkin G. V., O sopostavlenii novykh metodov pomekhoustoichivogo kodirovaniya (About comparison of new error correction coding methods), Tsifrovaya obrabotka signalov i ee primenenie, Proc. 18th Intern. Conf., Moscow, 2016, Vol. 1, pp. 59–65.
  10. Zolotarev V. V., Ovechkin P. V., Sposob kodirovaniya i dekodirovaniya blokovogo koda s ispol’zovaniem algoritma Viterbi (A method for encoding and decoding of block code with using of Viterbi algorithm), Patent RU 2608872, Reg. 25.01.2017.
  11. Zolotarev V. V., Zubarev Yu. B., Ovechkin G. V., Mnogoporogovye dekodery i optimizatsionnaya teoriya kodirovaniya (Multithreshold decoders and optimization coding theory), Moscow: Goryachaya liniya — Telekom, 2012, 238 p.
  12. Zolotarev V. V., Zubarev Yu. B., Ovechkin G. V., Averin S. V., Ovechkin P. V., 25 let optimizatsionnoi teorii kodirovaniya: novye perspektivy (25 years of optimization coding theory: new perspectives), Problemy peredachi i obrabotki informatsii v setyakh i sistemakh telekommunikatsii, Proc. 18th Intern. Scientific and Technological Conf., 2015, pp. 10–17.
  13. Zolotarev V. V., Ovechkin G. V., Nazirov R. R., O peredache Optimizatsionnoi Teorii liderstva ot prikladnoi klassicheskoi teorii pomekhoustoichivogo kodirovaniya (Optimization Theory: the Reception of the Baton of Leadership from the Applied Classic Theory of Error-Correcting Coding), In: Nekotorye aspekty sovremennykh problem mekhaniki i informatiki: sbornik nauchnykh statei, Moscow: IKI RAN, 2018, pp. 82–90.
  14. Zubarev Yu. B., Zolotarev V. V., Ovechkin G. V., Novye tekhnologii i paradigmy pomekhoustoichivogo kodirovaniya: posle resheniya problemy Shennona (New technologies and paradigms of error correction coding: after solving of Shannon problem), Elektrosvyaz’, 2019, No. 9, pp. 56–61, available at http://www.mtdbest.ru/articles/elsv2020.pdf.
  15. Zyablov V. V., Rybin P. S., Ispravlenie stiranii kodami s maloi plotnost’yu proverok (Recovering erasures with low density codes), Problemy peredachi informatsii, 2009, Vol. 45, pp. 15–32.
  16. Zyablov V. V., Rybin P. S., Analiz svyazi svoistv MPP-kodov i grafa Tannera (The analysis of connection between properties of LDPC codes and Tanner graph), Problemy peredachi informatsii, 2012, Vol. 48, pp. 3–29.
  17. Zyablov V. V., Iokhannesson R., Lonchar M., Prosto dekodiruemye kody s maloi plotnost’yu proverok na osnove kodov Khemminga (Simple for decoding low density parity check codes based on Hamming codes), Problemy peredachi informatsii, 2009, Vol. 45, pp. 25–40.
  18. Kudryashov B. D., Osnovy teorii kodirovaniya (Basics of error correction codes), Saint Petersburg: BKhV-Sankt-Peterburg, 2016, 393 p.
  19. Kuznetsov N. A., Zolotarev V. V., Ovechkin G. V., Ovechkin P. V., Nedvoichnye mnogoporogovye dekodery i drugie metody korrektsii oshibok v simvol’noi informatsii (Non-binary multithreshold decoders and other methods for error correction in symbolical information), Radiotekhnika, 2010, No. 6, pp. 4–9.
  20. Kuznetsov N. A., Zolotarev V. V., Zubarev Yu. B., Ovechkin G. V., Nazirov R. R., Averin S. V., Problemy i otkrytiya Optimizatsionnoi Teorii pomekhoustoichivogo kodirovaniya (Problems and discoveries of optimization error correction coding theory), Moscow: Goryachaya liniya — Telekom, 2020, 36 p., available at http://www.mtdbest.ru/articles/comics.pdf.
  21. Magarshak Yu., Chislo, vozvedennoe v absolyut (Elevating number to an absolute), Nezavisimaya gazeta, 09.09.2009, abailable at: https://www.ng.ru/science/2009-09-09/11_maths.html.
  22. Miloslavskaya V. D., Metody postroeniya i dekodirovaniya polyarnykh kodov: Diss. kand. tekhn. nauk (Methods for construction and decoding of polar codes, Cand. techn. sci. thesis), Saint Petersburg, 2015, 206 p.
  23. Morozov R. A., Dekodirovanie polyarnykh kodov s pomoshch’yu algoritma Dumera – Shabunova (Decoding polar codes using the Dumer – Shabunov algorithm), Spisok-2013: materialy vserossiiskoi nauchnoi konferentsii po problemam informatiki, Saint Petersburg: Izd. VVM, 2013, pp. 261–262, available at spisok.math.spbu.ru/2013/txt/papers/s7_1.odt.
  24. Nazarov L. E., Sheglov M. A., Kharakteristiki polnykh i ukorochennykh pomekhoustoichivykh nizkoplotnostnykh kodov na osnove konechnykh geometrii (Characteristics of length-compatible low-density parity-check codes on finite geometries), Uspekhi sovremennoi radioelektroniki, 2017, No. 6, pp. 38–48.
  25. Piterson U., Ueldon E., Kody, ispravlyayushchie oshibki (Codes correcting errors), Moscow: Mir, 1976, 594 p.
  26. Trifonov P. V., Metody postroeniya i dekodirovaniya mnogochlennykh kodov: Diss. dokt. tekhn. nauk (Methods for construction and decoding of multi-partition codes, Dr. techn. sci. thesis), Saint Petersburg, 2018, 254 p.
  27. Fedorenko S. V., Metody bystrogo dekodirovaniya lineinykh blokovykh kodov (Methods of fast decoding for linear block codes), Saint Petersburg, 2008, 198 p.
  28. Ammar H., Optimisation and analysis of polar codes in communication systems: Doctoral Thesis, University of Manchester, 2018, 177 p.
  29. Arikan E., Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels, IEEE Trans. Information Theory, 2009, Vol. 55, No. 7, pp. 3051–3073.
  30. Dumer I., Shabunov K., Soft-Decision Decoding of Reed-Muller Codes: Recursive Lists, IEEE Trans. Information Theory, 2006, Vol. 52, No. 3, pp. 1260–1266.
  31. Giard P., Sarkis G., Thibeault C., Gross W. J., Fast Software Polar Decoders, Proc. IEEE Intern. Conf. Acoustics, Speech and Signal Processing (ICASSP), 2014, 5 p.
  32. Ozgur U., A Performance Comparison of Polar Codes with Convolutional Turbo Codes: Doctoral Thesis, 2009, 166 p.
  33. Sarkis G., Giard P., Vardy A., Thibeault G., Gross W. J., Fast list decoders for polar codes, IEEE J. Selected Areas in Communications, 2016, Vol. 34, No. 2, pp. 318–328.
  34. Seidl M., Huber J. B., An Efficient Length- and Rate-Preserving Concatenation of Polar and Repetition Codes, Computer Science, Mathematics, 2013.
  35. Tal I., Vardy A., List decoding of polar codes, IEEE Trans. Information Theory, 2015, Vol. 61, pp. 2213–2226.
  36. Zolotarev V. V., Coding Theory as a Simple Optimal Decoding near Shannon’s Bound (Optimization Theory of error-correcting coding — is a new “quantum mechanics” of information theory), Moscow: Hot Line — Telecom, 2018, 333 p., available at https://mtdbest.ru/articles/mtd_book_2019.pdf.
  37. Zolotarev V. V., Zubarev Yu. B., Ovechkin G. V., Optimization Coding Theory and Multithreshold Algorithms, Switzerland: ITU, 2015, 158 p., available at https://mtdbest.ru/articles/Zolotarev_ITU.pdf.
  38. Zolotarev V., Ovechkin G., Ovechkin P., Satybaldina D., Tashatov N., Sankibayev D., High Throughput Software Multithreshold Decoder on GPU, 3rd Intern. Conf. Mathematics and Computers in Sciences and in Industry (MCSI), 2016.
  39. Zolotarev V. V., Ovechkin G. V., Chulkov I. V., Ovechkin P. V., Averin S. V., Satybaldina D. Zh., Kao V. T., Review of Achievements in the Optimization Coding Theory for Satellite Channels and Earth Remote Sensing Systems: 25 Years of Evolution, Sovremennye problemy distantsionnogo zondirovaniya Zemli iz kosmosa, 2017, Vol. 14, No. 1, pp. 9–24.