Sovremennye problemy distantsionnogo zondirovaniya Zemli iz kosmosa, 2014, Vol. 11, No. 2, pp. 138-151
Methods for speed of decoders for symbolic codes improvement
V.V. Zolotarev
1 , I.V. Chulkov
1 , G.V. Ovechkin
1 , D.J. Satibaldina
2 1 Space Research Institute RAS, Moscow, Russia
2 L.N. Gumilyov Eurasian National University, Astana, Republic of Kazakhstan
In some communication and data storage systems, non-binary (symbol) error-correcting codes are preferable use. The known symbol error-correction codes, such as Reed-Solomon codes and q-ary low-density parity-check codes, are shown to have either low symbol error rate performance or high implementation complexity. Symbolic multithreshold decoders (qMTD) for symbolic self orthogonal codes (qSOC) are also discussed. It is shown that qMTD performs almost optimal decoding for qSOC with low error-propagation at only linear complexity dependence on code length. Operations performed with symbolic threshold element (qTE) are analyzed. It is the most complex part of qMTD. The complexity of usual software implementation of qTE is proportional to d2, where d is the code distance. Several methods for qTE speed improvement with different memory requirements are proposed. These methods provide essential decrease in the number of arithmetic operations in comparison with non-optimized implementation of qTE. The best of the proposed methods can provide the algorithmic complexity O(d). As a result, qMTD decoding speed is increased two or even more times for standard code parameters in comparison with usual qTE algorithm without performance loss.
Keywords: iterative decoding, symbolic (q-ary) multithreshold decoders, symbolic self-orthogonal codes, threshold element, decoding complexity.
Full textReferences:
- Zolotarev V.V., Zubarev Yu.B., Ovechkin G.V. Mnogoporogovye dekodery i optimizatsionnaya teoriya kodirovaniya (Multithreshold decoders and optimizing coding theory), Moscow: Goryachaya liniya-Telekom, 2012, 239 p.
- Zolotarev V.V., Zubarev Yu.B., Ovechkin G.V. Obzor metodov pomekhoustoichivogo kodirovaniya s ispol'zovaniem mnogoporogovykh algoritmov (Overview of error-correcting coding methods are used multithreshold algorithms), Tsifrovaya obrabotka signalov, 2008, No. 1, pp.2–11.
- Zolotarev V.V., Zubarev Yu.B., Ovechkin G.V., Dmitrieva T.A. Mnogoporogovye algoritmy dlya sputnikovykh setei s optimal'nymi kharakteristikami (Multithreshold algorithms with optimal performance for satellite communications), Elektrosvyaz', 2006, No. 10, pp. 9–11.
- 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.
- Ovechkin G.V., Ovechkin P.V. Ispol'zovanie nedvoichnogo mnogoporogovogo dekodera v kaskadnykh skhemakh korrektsii oshibok (The using of non-binary multithreshold decoder in concatenated error-correction schemes), Vestnik RGRTU, 2009, No. 4, Issue 30, pp. 7–12.
- Berlekamp E. R. Algebraic Coding Theory, McGraw-Hill, New York, 1968.
- Massey J. Threshold decoding, M.I.T. Press, Cambridge, Massachusetts, 1963.
- Ullah M.A., Okada K., Ogivara H. Multi-Stage Threshold Decoding for Self-Orthogonal Convolutional Codes, IEICE Trans. Fundamentals, Vol.E93-A, No. 11, pp. 19321941, Nov. 2010.
- Wu C. New list decoding algorithms for Reed-Solomon and BCH codes, IEEE Transactions on Information Theory, Vol. 54, pp. 36113630, August 2008.
- Zhang F., Pfister H. List-Message Passing Achieves Capacity on the q-ary Symmetric Channel for Large q, Proc. IEEE Global Telecom. Conf. , Washington, DC, pp. 283–287, Nov. 2007.