Abstract:
قابلیت کدهای کانولوشنال در تصحیح خطا با افزایش طول حافظه افزایش مییابد. اما افزایش طول حافظه، باعث افزایش پیچیدگی الگوریتم کدگشایی بهینه ویتربی میشود، چرا که تعداد محاسبات در الگوریتم ویتربی بهصورت نمایی بهطول حافظه وابسته است. افزایش پیچیدگی الگوریتم ویتربی با طول حافظه، میتواند پیادهسازی این الگوریتم را هنگام کدگشایی کدهای کانولوشنال با طول حافظه بلند ناممکن کند. به همین جهت الگوریتمهای زیربهینهای همانند Fano و Stack ارائه شدهاند تا امکان کدگشایی ترتیبی و سریع کدهای کانولوشنال با طول حافظه بلند را فراهم کنند. در این نوشتار به معرفی شیوههای گوناگون پیادهسازی الگوریتمهای Fano و Stack پرداخته و با ارائه نوآوریهایی، سرعت اجرا و حافظه مورد نیاز این الگوریتمها را بهبود میدهیم. برای ارزیابی مزایای پیادهسازیهای مختلف ارائهشده، آنها را برمبنای قدرت تصحیح خطا، زمان کدگشایی و میزان حافظه مورد نیاز مقایسه میکنیم. همچنین ما از نتایج شبیه سازی استفاده میکنیم تا نشان دهیم که اگر وضعیت کانال مخابره زیاد خراب نباشد، الگوریتمهای Fano و Stack میتوانند توانایی تصحیح خطای الگوریتم بهینه ویتربی را در زمان کدگشایی بسیار کمتر، برای کدگشایی کدهای کانولوشنال با طول حافظه بلند فراهم آورند
Machine summary:
همچنین ما از نتایج شبیه سازی استفاده میکنیم تا نشان دهیم که اگر وضعیت کانال مخابره زیاد خراب نباشد، الگوریتمهای Fano و Stack میتوانند توانایی تصحیح خطای الگوریتم بهینه ویتربی را در زمان کدگشایی بسیار کمتر، برای کدگشایی کدهای کانولوشنال با طول حافظه بلند فراهم آورند .
در پیادهسازی نسخه سوم، این نکته را مد نظر قرارداده و بهصورت پویا ضمن اجرای الگوریتم، قسمت مشترک مسیرهای موجود در پشته را بهعنوان قسمتی از رشته بیت کدگشاییشده به خروجی منتقل میکنیم.
3-1-4-نسخه چهارم پیادهسازی الگوریتم Stack اگر شرایط کانال به اندازه کافی مناسب باشد میتوان عرض پشته برای ذخیره مسیرهای کدگشاییشده را نیز بهعنوان پارامتر ورودی دریافت و به اندازه دلخواه محدود کرد.
3-1-6- نسخه ششم پیادهسازی الگوریتم Stack در پیادهسازیهای پیشین تمام رشته بیت کدشده دریافتی اتخاذ و سپس فرایند کدگشایی ترتیبی روی آن اعمال میگردد.
3-2-3- نسخه سوم پیادهسازی الگوریتم Fano در پیادهسازیهای پیشین تمام رشته بیت کدشده دریافتی اتخاذ و سپس فرایند کدگشایی ترتیبی روی آن اعمال میگردد.
در این تصاویر زمان کدگشایی یک رشته بیت کدشده با کد کانولوشنال[1111001 1011011] بر حسب طول دنباله کدگشاییشده برای نسخههای متفاوت پیادهسازیشده، ترسیم شده است.
در این شکل درصد خطای دنباله کدگشایی شده بر حسب خطای کانال برای الگوریتمهای Fano (پیادهسازی نسخه دوم)، Stack (پیادهسازی نسخه سوم) و ویتربی مقایسه شدهاند.
نتایج شبیهسازی نشان دادند که الگوریتمهای Fano و Stack در مقایسه با الگوریتم ویتربی میتوانند در زمان بسیار کوتاهتر یک رشته بیت کدشده با کد کانولوشنال با طول حافظه بلند را کدگشایی کنند.