しきい値復号法によるSpinal符号

摘要

Spinal符号(まレートレス符号の新たなクラスであり，加法性白色ガウス雑音通信路において通信路容量に 漸近するレートを達成する.Spinal符号の復号は符号木上の探索により行われるが，従来の復号ァルゴリズムではソートに起因するボトルネックが存在し，システムのスループットを向上させる上で問題となる.本稿ではソートを用いな い，しきい値復号法によるSpinal符号の特性を明らかにする.しきい値復号法としてT-アルゴリズム，メトリック値にもとづくしきい値アルゴリズムについて検討し，しきい値復号法が高い並列性を実現し，計算複雑性とスループットの観点において有効な復号法であることを示す.%Spinal codes are a recently proposed rateless code that achieves Shannon capacity on additive white Gaussian noise channel. Some breadth-first tree search algorithms are introduced for decoding spinal codes, however, sorting operations of conventional decoding algorithms remain as critical throughput bottleneck. To achieve higher throughput of the decoder, non-sorting algorithms and highly parallerism are attractive. In this paper, we investigate a property of threshold algorithms for decoding spinal codes, i.e., T-algorithm and metric-based threshold algorithm. These algorithms are evaluated from the view points of computational complexity and throughput, and we demonstrate the superiority of threshold decoding algorithms.