Theoretical and Experimental Upper and Lower Bounds on the Efficiency of Convolutional Codes in a Binary Symmetric Channel
Tóm tắt
We propose a new approach to the analytical estimation of the error burst probability, the probability of erroneous decoding, and the probability of error per bit for convolutional codes with Viterbi decoding in a binary symmetric channel (BSC). Upper and lower estimates of the probability of error per bit and of the erroneous decoding probability are based on active distances and the distance spectrum of active distances for a convolutional code. The estimates are derived for rate
$${1}/{2}$$
convolutional codes, but they can also be generalized to any convolutional code with rate
$${1}/{n}$$
. Calculation of the estimates described here has linear time complexity in the error burst minimal length if code distance properties are known. The computational complexity does not depend on the crossover probability of a BSC. Simulation results show that the considered estimates are rather tight, especially for small crossover probabilities.
Tài liệu tham khảo
Elias, P., Coding for Noisy Channels, IRE Conv. Rec., 1955, vol. 4, pp. 37–46. Reprinted in Key Papers in the Development of Information Theory, Slepian, D., Ed., New York: IEEE Press, 1974, pp. 102–111.
Yang, C., Zhan, M., Deng, Y., Wang, M., Luo, X.H., and Zeng, J., Error-Correcting Performance Comparison for Polar Codes, LDPC Codes and Convolutional Codes in High-Performance Wireless, in Proc. 6th Int. Conf. on Information, Cybernetics, and Computational Social Systems (ICCSS’2019), Chongqing, China, Sept. 27–30, 2019, P. 258–262. https://doi.org/10.1109/ICCSS48103.2019.9115442
Deng, Y., Zhan, M., Wang, M., Yang, C., Luo, X., Zeng, J., and Guo, J., Comparing Decoding Performance of LDPC Codes and Convolutional Codes for Short Packet Transmission, in Proc. IEEE 17th Int. Conf. on Industrial Informatics (INDIN’2019), Helsinki, Finland, July 22–25, 2019,vol. 1, pp. 1751–1755. https://doi.org/10.1109/INDIN41052.2019.8972062
Tahir, B., Schwarz, S., and Rupp, M., BER Comparison between Convolutional, Turbo, LDPC, and Polar Codes, in Proc. 24th Int. Conf. on Telecommunications (ICT’2017), Limassol, Cyprus, May 3–5, 2017, pp. 1–7. https://doi.org/10.1109/ICT.2017.7998249
Rurik, W. and Mazumdar, A., Hamming Codes as Error-Reducing Codes, in Proc. 2016 IEEE Information Theory Workshop (ITW’2006), Cambridge, UK, Sept. 11–14, 2016, pp. 404–408. https://doi.org/10.1109/ITW.2016.7606865
Liu, K. and García-Frías, J., Error Floor Analysis in LDGM Codes, in Proc. 2010 IEEE Int. Symp. on Information Theory (ISIT’2010), Austin, TX, USA, June 13–18, 2010, pp. 734–738. https://doi.org/10.1109/ISIT.2010.5513607
Gao, W. and Polyanskiy, Y., On the Bit Error Rate of Repeated Error-Correcting Codes, in Proc. 48th Annu. Conf. on Information Sciences and Systems (CISS’2014), Princeton, NJ, USA, Mar. 19–21, 2014, pp. 1–6. https://doi.org/10.1109/CISS.2014.6814087
Höst, S., Johannesson, R., and Zyablov, V.V., Woven Convolutional Codes I: Encoder Properties, IEEE Trans. Inform. Theory, 2002, vol. 48, no. 1, pp. 149–161. https://doi.org/10.1109/18.971745
Freudenberger, J., Bossert, M., Shavgulidze, S., and Zyablov, V., Woven Turbo Codes, in Proc. 7th Int. Workshop on Algebraic and Combinatorial Coding Theory (ACCT’2000), Bansko, Bulgaria, June 18–24, 2000, pp. 145–150. Available at http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.345&rep=rep1&type=pdf
Benedetto, S. and Montorsi, G., Design of Parallel Concatenated Convolutional Codes, IEEE Trans. Commun., 1996, vol. 44, no. 5, pp. 591–600. https://doi.org/10.1109/26.494303
Berrou, C., Glavieux, A., and Thitimajshima, P., Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes. 1, in Proc. IEEE Int. Conf. on Communications (ICC’93), Geneva, Switzerland, May 23–26, 1993, vol. 2, pp. 1064–1070. https://doi.org/10.1109/ICC.1993.397441
Douillard, C. and Berrou, C., Turbo Codes with Rate-m/(m+1) Constituent Convolutional Codes, IEEE Trans. Commun., 2005, vol. 53, no. 10, pp. 1630–1638. https://doi.org/10.1109/TCOMM.2005.857165
Zhang, Q., Liu, A., Zhang, Y., and Liang, X., Practical Design and Decoding of Parallel Concatenated Structure for Systematic Polar Codes, IEEE Trans. Commun., 2016, vol. 64, no. 2, pp. 456–466. https://doi.org/10.1109/TCOMM.2015.2502246
Viterbi, A.J., Convolutional Codes and Their Performance in Communication Systems, IEEE Trans. Commun. Technol., 1971, vol. 19, no. 5, pp. 751–772. https://doi.org/10.1109/TCOM.1971.1090700
van De Meeberg, L., A Tightened Upper Bound on the Error Probability of Binary Convolutional Codes with Viterbi Decoding, IEEE Trans. Inform. Theory, 1974, vol. 20, no. 3, pp. 389–391. https://doi.org/10.1109/TIT.1974.1055216
Herro, M., Hu, L., and Nowack, J., Bit Error Probability Calculations for Convolutional Codes with Short Constraint Lengths on Very Noisy Channels, IEEE Trans. Commun., 1988, vol. 36, no. 7, pp. 885–888. https://doi.org/10.1109/26.2819
Chiaraluce, F., Gambi, E., Mazzone, M., and Pierleoni, P., A Technique to Evaluate an Exact Formula for the Bit Error Rate of Convolutional Codes in Case of Finite Length Words, Proc. IEEE Region 10 Annu. Conf. on Speech and Image Technologies for Computing and Telecommunications (IEEE TENCON’97), Queensland Univ. of Technology, Brisbane, Australia, Dec. 2–4, 1997, Deriche, M., Moody, M., and Bennamoun, M., Eds., vol. 1, pp. 113–116. https://doi.org/10.1109/TENCON.1997.647271
Forney, G., The Viterbi Algorithm, Proc. IEEE, 1973, vol. 61, no. 3, pp. 268–278. https://doi.org/10.1109/PROC.1973.9030
Yoshikawa, H., Theoretical Analysis of Bit Error Probability for Punctured Convolutional Codes, in Proc. 2012 IEEE Int. Sympos. on Information Theory and Its Applications (ISITA’2012), Honolulu, HI, USA, Oct. 28–31, 2012, pp. 658–661.
Bocharova, I.E., Hug, F., Johannesson, R., and Kudryashov, B.D., A Closed-Form Expression for the Exact Bit Error Probability for Viterbi Decoding of Convolutional Codes, IEEE Trans. Inform. Theory, 2012, vol. 58, no. 7, pp. 4635–4644. https://doi.org/10.1109/TIT.2012.2193375
Smeshko, A., Ivanov, F., and Zyablov, V., Theoretical Estimates of Burst Error Probability for Convolutional Codes, in Proc. 2020 Int. Symp. on Information Theory and Its Applications (ISITA’2020), Kapolei, HI, USA, Oct. 24–27, 2020, pp. 136–140.
Smeshko, A., Ivanov, F., and Zyablov, V., The Influence of Active Distances on the Distribution of Bursts, in Proc. XVI Int. Symp. “Problems of Redundancy in Information and Control Systems” (REDUNDANCY’2019), Moscow, Russia, Oct. 21–25, 2019, pp. 110–114. https://doi.org/10.1109/REDUNDANCY48165.2019.9003349
Smeshko, A., Ivanov, F., and Zyablov, V., Upper and Lower Estimates of Frame Error Rate for Convolutional Codes, Proc. 2020 Int. Symp. on Information Theory and Its Applications (ISITA’2020), Kapolei, HI, USA, Oct. 24–27, 2020, pp. 160–164.
Kudryashov, B.D., Osnovy teorii kodirovaniya (Fundamentals of Coding Theory), St. Petersburg: BHV-Petersburg, 2016.
Höst, S., Johannesson, R., Zigangirov, K., and Zyablov, V., Active Distances for Convolutional Codes, IEEE Trans. Inform. Theory, 1999, vol. 45, no. 2, pp. 658–669. https://doi.org/10.1109/18.749009
Miller, R.L., Deutsch, L.J., and Butman, S.A., On the Error Statistics of Viterbi Decoding and the Performance of Concatenated Codes, NASA STI/Recon Tech. Rep., Sept. 1, 1981, no. 81-33364. Available at https://archive.org/details/nasa_techdoc_19810024821
Justesen, J. and Andersen, J., Critical Lengths of Error Events in Convolutional Codes, IEEE Trans. Inform. Theory, 1998, vol. 44, no. 4, pp. 1608–1611. https://doi.org/10.1109/18.681339
[GitHub online repository], 2021. https://github.com/smeshk/Active-distances-their-spectrum-and-estimates-for-convolutional-code