350 rub
Journal Radioengineering №6 for 2010 г.
Article in number:
Non-Bynary Multithreshold Decoders and Other Error-Correction Methods in Symbolical Data
Keywords: error-correcting coding communication systems data storage systems q-ary symmetric channel non-binary codes Reed-Solomon codes non-binary self-orthogonal codes non-binary multithreshold decoder non-binary low-density parity-check codes
Authors:
N.A. Kuznetsov, V.V. Zolotarev, G.V. Ovechkin, P.V. Ovechkin
Abstract:
The article deals with main modern non-binary codes and algorithms of their decoding. They are Reed-Solomon codes, non-binary low-density parity-check codes and non-binary self-orthogonal codes, decoded with non-binary multithreshold decoder (qMTD). We shown the non-binary multithreshold decoders (qMTD) of self-orthogonal codes are the best by performance and complexity ratio. qMTD with linear implementation complexity provide in hundreds times better correcting ability than Reed-Solomon codes which have much more imple-mentation complexity. It is shown non-binary low-density parity-check codes provide impressive performance. However complexity of its decoding depends of the alphabet size. As a result using of these codes with large symbols is difficultly. It-s discussed capability of non-binary codes application for protection of files against errors in data storage systems. We shown the using software based on qMTD for this purpose often allows to provide better level of protection and higher speed of coding and decoding simultaneously than analogs. Additional advantage of the software qMTD is capability of correction as bursts of errors as independent errors.
Pages: 4-9
References
  1. Low-Density Parity-Check Codes with Rates Very Close to the Capacity of the q-ary Symmetric Channel for Large q // ISIT 2004, Chicago, USA, June 27 - July 2, 2004. P. 273.
  2. Reed I.S., Solomon G. Polynomial codes over certain finite fields // J. Soc. Industrial Appl. Math. 1960. V.8. P. 300-304.
  3. ПитерсонУ., УэлдонЭ.Коды, исправляющиеошибки. М.: Мир. 1976.
  4. Ning C., Zhiyuan Y. Complexity analysis of Reed-Solomon decoding over GF(2m) without using syndromes // EURASIP Journal on Wireless Communications and Networking, January. 2008. № 4. P.1-11,
  5. Sudan M. Decoding of Reed Solomon codes beyond the error-correction bound // Journal of Complexity. 1997. V.13. P.180-193.
  6. Золотарёв В.В. Каскадные схемы МПД-декодирования для больших баз данных // Мобильные системы. 2008. № 3. С.66-71.
  7. Золотарёв В.В., Овечкин Г.В. Эффективное многопороговое декодирование недвоичных кодов // Радиотехника и электроника. 2010. Т. 55. № 3. С.324-329.
  8. Золотарёв В.В. Теория и алгоритмы многопорогового декодирования. М.: Радио и связь. Горячая линия - Телеком. 2006.
  9. Золотарёв В.В. Обобщение алгоритма МПД на недвоичные коды // Мобильные системы. 2007. №3. С. 39-42.
  10. Многопороговые декодеры. Веб-сайт ИКИ РАН www.mtdbest.iki.rssi.ru.
  11. Золотарёв В.В. Параллельное кодирование в каналах СПД // Вопросы кибернетики. 1986. Вып. 120.
  12. Овечкин Г.В., Овечкин П.В. Оптимизация структуры недвоичных самоортогональных кодов для схем параллельного кодирования // Труды НИИР. 2009. №2.
  13. Davey M.C., MacKay D.J.C. Low density parity check codes over GF(q) // IEEE Comm. Letters, 2(6). 1998. P.165-167.
  14. Declercq D., Fossorier M. Extended minsum algorithm for decoding LDPC codes over GF(q) // IEEE International Symp. on Inf. Theory. 2005. P.464-468.
  15. Zhang F., Pfister H. List-Message Passing Achieves Capacity on the q-ary Symmetric Channel for Large q // In Proc.
    IEEE Global Telecom. Conf., Washington, DC, Nov. 2007.
    P.283-287.
  16. www.quickpar.org.uk
  17. www.ice-graphics.com
  18. Овечкин П.В. Применение недвоичного многопорогового декодера для защиты файлов от искажений // В сб.: 11 Международная конференция «Цифровая обработка сигналов и ее приложения- DSPA-09». 2009. C. 200-202.