シフト演算を利用した噴水符号に対するスケジューリングを用いた逐次的反復復号法の効率化

摘要

噴水符号はインターネットにおけるマルチキャストの信頼性を向上させる消失訂正符号である．シフト演算を利用した噴水（ZDF：Zigzag Decodable Fountain）符号は，Raptor符号を一般化した符号であり，送信パケットを作成する際にシフト演算を利用する．シフト演算を利用したことによって，Raptor符号と同様の復号をした後に，ビット毎の復号をすることができる．そのため，ZDF符号はRaptor符号よりも低い復号消失率を達成している．しかし，ビット毎の復号では全ての受信パケットを逐次的に処理しているため，復号にかかる時間が大きい．本稿ではZDF符号の復号時間の短縮を目的とする．この目的を達成するために，ZDF符号におけるビット毎の逐次反復復号法の改良をする．この手法では，通常の復号手順を用いて復号に貢献したエッジの集合をわりだし，その集合の内で復号に貢献した順にリストに記録する．その後はこのリストの順に復号をすることで高速化をはかる．その結果，復号消失率をほとんど低下させずに，復号時間の短縮に成功した．