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

Sequential Decoding Algorithms of Convolutional Codes: Implementation, Improvement and Comparison

قابليت كدهاي كانولوشنال در تصحيح خطا با افزايش طول حافظه افزايش مي‌يابد. اما افزايش طول حافظه، باعث افزايش پيچيدگي الگوريتم كدگشايي بهينه ويتربي مي‌شود، چرا كه تعداد محاسبات در الگوريتم ويتربي به صورت نمايي به طول حافظه وابسته است. افزايش پيچيدگي الگوريتم ويتربي با طول حافظه، مي‌تواند پياده‌سازي اين الگوريتم را هنگام كدگشايي كدهاي كانولوشنال با طول حافظه بلند ناممكن كند. به همين جهت الگوريتم‌هاي زيربهينه اي همانند Fano و Stack ارايه شده‌اند تا امكان كدگشايي ترتيبي و سريع كدهاي كانولوشنال با طول حافظه بلند را فراهم كنند. در اين نوشتار به معرفي شيوه‌هاي گوناگون پياده‌سازي الگوريتم‌هاي Fano و Stack پرداخته و با ارايه نوآوري‌هايي، سرعت اجرا و حافظه مورد نياز اين الگوريتم‌ها را بهبود مي‌دهيم. براي ارزيابي مزاياي پياده‌سازي‌هاي مختلف ارايه شده، آن‌ها را برمبناي قدرت تصحيح خطا، زمان كدگشايي و ميزان حافظه مورد نياز مقايسه مي‌كنيم. همچنين ما از نتايج شبيه سازي استفاده مي‌كنيم تا نشان دهيم كه اگر وضعيت كانال مخابره زياد خراب نباشد، الگوريتم‌هاي Fano و Stack مي‌توانند توانايي تصحيح خطاي الگوريتم بهينه ويتربي را در زمان كدگشايي بسيار كمتر، براي كدگشايي كدهاي كانولوشنال با طول حافظه بلند فراهم آورند.

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.