مقایسه و بهبود پیاده‌سازی الگوریتم‌های کدگشایی ترتیبی کدهای کانولوشنال

هادی, محمد; پاکروان, محمدرضا

تعداد نشریات	36
تعداد شماره‌ها	1,192
تعداد مقالات	8,579
تعداد مشاهده مقاله	6,989,897
تعداد دریافت فایل اصل مقاله	4,033,387

	مقایسه و بهبود پیاده‌سازی الگوریتم‌های کدگشایی ترتیبی کدهای کانولوشنال
پدافند الکترونیکی و سایبری
مقاله 5، دوره 3، شماره 2، مرداد 1394، صفحه 61-73 اصل مقاله (875.84 K)
نویسندگان
محمد هادی^* ¹؛ محمدرضا پاکروان²
¹دانشجوی دکترای مخابرات، دانشگاه صنعتی شریف، تهران، ایران
²دانشیار، دانشگاه صنعتی شریف، تهران، ایران
تاریخ دریافت: 01 فروردین 1394، تاریخ بازنگری: 31 خرداد 1402، تاریخ پذیرش: 28 شهریور 1397
چکیده
قابلیت کدهای کانولوشنال در تصحیح خطا با افزایش طول حافظه افزایش می‌یابد. اما افزایش طول حافظه، باعث افزایش پیچیدگی الگوریتم کدگشایی بهینه ویتربی می‌شود، چرا که تعداد محاسبات در الگوریتم ویتربی به صورت نمایی به طول حافظه وابسته است. افزایش پیچیدگی الگوریتم ویتربی با طول حافظه، می‌تواند پیاده‌سازی این الگوریتم را هنگام کدگشایی کدهای کانولوشنال با طول حافظه بلند ناممکن کند. به همین جهت الگوریتم‌های زیربهینه ای همانند Fano و Stack ارائه شده‌اند تا امکان کدگشایی ترتیبی و سریع کدهای کانولوشنال با طول حافظه بلند را فراهم کنند. در این نوشتار به معرفی شیوه‌های گوناگون پیاده‌سازی الگوریتم‌های Fano و Stack پرداخته و با ارائه نوآوری‌هایی، سرعت اجرا و حافظه مورد نیاز این الگوریتم‌ها را بهبود می‌دهیم. برای ارزیابی مزایای پیاده‌سازی‌های مختلف ارائه شده، آن‌ها را مبنای قدرت تصحیح خطا، زمان کدگشایی و میزان حافظه مورد نیاز مقایسه می‌کنیم. همچنین ما از نتایج شبیه سازی استفاده می‌کنیم تا نشان دهیم که اگر وضعیت کانال مخابره زیاد خراب نباشد، الگوریتم‌های Fano و Stack می‌توانند توانایی تصحیح خطای الگوریتم بهینه ویتربی را در زمان کدگشایی بسیار کمتر، برای کدگشایی کدهای کانولوشنال با طول حافظه بلند فراهم آورند.
کلیدواژه‌ها
کدهای کانولوشنال؛ الگوریتم‌های کدگشایی ترتیبی کدهای کانولوشنال؛ الگوریتم ویتربی؛ الگوریتم Fano؛ الگوریتم Stack؛ طول حافظه کد کانولوشنال
عنوان مقاله [English]
Sequential Decoding Algorithms of Convolutional Codes: Implementation, Improvement and Comparison
نویسندگان [English]
Mohammad Hadi¹؛ Mohammad Reza Pakravan²
¹Doctoral student of telecommunications, Sharif University of Technology, Tehran, Iran
²Associate Professor, Sharif University of Technology, Tehran, Iran
چکیده [English]
Error correction capability of convolutional codes is improved by increasing code constraint length. However, increasing the constraint length results in high complexity of optimum Viterbi decoding algorithm because the number of computations in Viterbi algorithm is exponentially proportional to the constraint length. Consequently, decoding of high constraint length convolutional codes using Viterbi algorithm may practically be impossible. Sub-optimum decoding algorithms such as Fano and Stack algorithms have been proposed to feasible fast sequential decoding of high constraint length convolutional codes. In this paper, we introduce different methods of implementing Fano and Stack algorithms and propose some techniques to improve their speed and required memory. We compare the introduced implementations of the algorithms in terms of error correction capability, decoding time and required memory. Furthermore, we use simulation results to show that if the communication error is low, Fano and Stack algorithms can provide the same error correction capability as the optimum Viterbi algorithm in very short decoding time
کلیدواژه‌ها [English]
Convolutional Codes, Sequential Decoding of Convolutional Codes, Viterbi Algorithm, Fano Algorithm, Stack Algorithm, Convolutional Code Constraint length

مراجع
[1] A. J. Viterbi, “Convolutional Codes and Their Performance in Communication Systems,” IEEE Transaction on Communication Technology, vol. COM-19, no. 5, pp. 751-772, Oct. 1971. [2] S. Lin and D. J. Costello, “Error Control Coding,” Prentice Hall, 2004. [3] S. Kim and S. B. Wicker, “Fundamentals of Codes Graphs and Iterative Decoding,” Springer, 2002. [4] J. B. Anderson, “Sequential Coding Algorithms: A Survey and Cost Analysis,” IEEE Transaction on Communications, vol. COM-32, no. 2, pp. 169-176, Feb. 1984. [5] S. H. Yunghsiang and C. Po-Ning, “Sequential Decoding of Convolutional Codes,” Wiley Encyclopedia of Telecommunications, Apr. 2003, Revised Jul. 2015. [6] J. M. Wozencraft, “Sequential Decoding for Reliable Communication,” IRE Nat. Conv. Rec., vol. 5, no. 2, pp. 11-25, 1957. [7] J. M. Wozencraft and B. Reiffen, “Sequential Decoding,” IEEE Trans. Inform. Theory, vol. IT-9, no. 2, pp. 64-73, April 1961. [8] R. M. Fano, “A Heuristic Discussion of Probabilistic Decoding,” IEEE Trans. Inform. Theory, vol. IT-9, no. 2, pp. 64-73, April 1963. [9] F. Jelinek, “A Fast Sequential Decoding Algorithm Using a Stack,” IBM J. Res. and Dev., vol. 13, pp. 675-685, November 1989. [10] K. S. Zigangirov, “Some Sequential Decoding Procedures,” Probl. Peredachi Inf., vol. 2, pp. 13-25, 1966. [11] J. L. Massey, “Variable Length Codes and The Fano Metric,” IEEE Trans. Inform. Theory, vol. IT-18, no. 1, pp. 196-198, January 1972. [12] E. A. Bucher, “Sequential Decoding of Systematic and Nonsystematic Convolutional Codes with Arbitrary Decoder Bias,” IEEE Trans. Inform. Theory, vol. IT-16, no. 5, pp. 611-624, September 1970. [13] F. Jelinek, “Upper bound on sequential decoding performance parameters,” IEEE Trans. Inform. Theory, vol. IT-20, no. 2, pp. 227-239, March 1974. [14] D. Haccoun and M. J. Ferguson, “Generalized Stack Algorithms for Decoding Convolutional Codes,” IEEE Trans. Inform. Theory, vol. IT-21, no. 6, pp. 638-651, November 1975. [15] J. M. Geist, “An Empirical Comparison of Two Sequential Decoding Algorithms,” IEEE Trans. Commun. Technol., vol. COM-19, no. 4, pp. 415-419, August 1971.
آمار تعداد مشاهده مقاله: 219 تعداد دریافت فایل اصل مقاله: 243

آمار

مقایسه و بهبود پیاده‌سازی الگوریتم‌های کدگشایی ترتیبی کدهای کانولوشنال