(57)【要約】本開示にかかる復号装置（１０）は、トレリス線図における時点Ｎの状態Ｓに向かうパスに対応するブランチラベルと、複数の受信信号系列とを用いて状態Ｓにおけるブランチメトリックを算出する多入力ブランチメトリック計算ユニット（１１）と、時点Ｎの状態Ｓにおけるパスメトリックを算出するパスメトリック計算ユニット（１２）と、算出された複数のパスメトリックのうち、Ｌ個のパスメトリックに対応するパスラベルを格納する生き残りパスリストメモリ（１３）と、を備える。パスメトリック計算ユニット（１２）は、時点Ｎの前記状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスラベルに、ブランチラベルを結合して時点Ｎの前記状態Ｓにおけるパスラベルを生成し、生き残りパスリストメモリ（１３）は、トレリス線図における終点において選択されたＬ個のパスメトリックに対応するパスラベルを送信信号系列として出力する。
2019234903.tif 000002
【特許請求の範囲】
【請求項１】
トレリス線図における時点Ｎ（Ｎは０以上の整数）の状態Ｓ（Ｓは０以上の整数）に向かうパスに対応するブランチラベルと、複数の受信信号系列とを用いて前記状態Ｓにおけるブランチメトリックを算出する多入力ブランチメトリック計算手段と、
前記時点Ｎの状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスメトリックに前記時点Ｎの前記状態Ｓにおけるブランチメトリックを加算して、前記時点Ｎの前記状態Ｓにおけるパスメトリックを算出するパスメトリック計算手段と、
算出された複数の前記パスメトリックのうち、Ｌ（Ｌは１以上の整数）個のパスメトリックに対応するパスラベルを格納する生き残りパスリストメモリと、を備え、
前記パスメトリック計算手段は、
前記時点Ｎの前記状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスラベルに、前記ブランチラベルを結合して前記時点Ｎの前記状態Ｓにおけるパスラベルを生成し、
前記生き残りパスリストメモリは、
前記トレリス線図における終点において選択されたＬ個のパスメトリックに対応するパスラベルを送信信号系列として出力する、復号装置。
【請求項２】
前記パスメトリックを算出する際に用いられた前記受信信号系列を指定するインデックスを格納するインデックスメモリをさらに備える、請求項１に記載の復号装置。
【請求項３】
算出された前記パスメトリックを格納するパスメトリックメモリをさらに備え、
前記パスメトリック計算手段は、
前記インデックスが示す前記受信信号系列を用いて算出された前記ブランチメトリックを、前記パスメトリックメモリに格納された前記時点Ｎ−１のそれぞれの状態におけるパスメトリックに加算する、請求項２に記載の復号装置。
【請求項４】
前記生き残りパスリストメモリは、
算出された複数の前記パスメトリックのうち、値の小さい順にＬ個のパスメトリックに対応するパスラベルを格納する、請求項１乃至３のいずれか１項に記載の復号装置。
【請求項５】
前記トレリス線図における終点は、状態数を１とし、
前記パスメトリック計算手段は、
前記トレリス線図における終点の１つの状態に向かうパスに対応するパスメトリックを算出し、さらに、パスラベルを生成する、請求項１乃至４のいずれか１項に記載の復号装置。
【請求項６】
長さＮ１（Ｎ１は１以上の整数）ビットのＰｏｌａｒ符号のデコード処理を実行し、リストサイズを１とするＳＣユニットをＬ個有する演算手段をさらに備え、
前記多入力ブランチメトリック計算手段は、
Ｎ２（Ｎ２は１以上の整数）個の前記演算手段から出力される長さＮ２ビットのＬ個の受信信号系列と前記ブランチラベルとを用いて前記ブランチメトリックを算出する、請求項１乃至５のいずれか１項に記載の復号装置。
【請求項７】
ビタビアルゴリズムを用いて１つの受信信号系列から算出された複数の送信信号系列のうち、尤度の高い順にＬ（Ｌは１以上の整数）個の送信信号系列を選択するリスト出力ビタビデコーダと、
Ｍ（Ｍは１以上の整数）個の前記リスト出力ビタビデコーダから出力されたＭ×Ｌ個の送信信号系列のうち、尤度の高い順に選択したＬ個の送信信号系列を出力する選択手段と、を備える復号装置。
【請求項８】
長さＮ１（Ｎ１は１以上の整数）ビットのＰｏｌａｒ符号のデコード処理を実行し、リストサイズを１とするＳＣユニットをＬ個有する演算手段をさらに備え、
前記リスト出力ビタビデコーダは、
Ｎ２（Ｎ２は１以上の整数）個の前記演算手段から出力される長さＮ２ビットの受信信号系列から複数の送信信号系列を算出する、請求項７に記載の復号装置。
【請求項９】
トレリス線図における時点Ｎ（Ｎは０以上の整数）の状態Ｓ（Ｓは０以上の整数）に向かうパスに対応するブランチラベルと、複数の受信信号系列とを用いて前記状態Ｓにおけるブランチメトリックを算出し、
前記時点Ｎの状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスメトリックに前記時点Ｎの前記状態Ｓにおけるブランチメトリックを加算して、前記時点Ｎの前記状態Ｓにおけるパスメトリックを算出し、
算出された複数の前記パスメトリックのうち、Ｌ（Ｌは１以上の整数）個のパスメトリックに対応するパスラベルを格納し、
前記時点Ｎの前記状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスラベルに、前記ブランチラベルを結合して前記時点Ｎの前記状態Ｓにおけるパスラベルを生成し、
前記トレリス線図における終点において選択されたＬ個のパスメトリックに対応するパスラベルを送信信号系列として出力する、復号方法。
【請求項１０】
ビタビアルゴリズムを用いて１つの受信信号系列から算出された複数の送信信号系列のうち、尤度の高い順にＬ（Ｌは１以上の整数）個の送信信号系列を選択し、
Ｍ（Ｍは１以上の整数）個のリスト出力ビタビデコーダから出力されたＭ×Ｌ個の送信信号系列のうち、尤度の高い順に選択したＬ個の送信信号系列を出力する、復号方法。
【請求項１１】
トレリス線図における時点Ｎ（Ｎは０以上の整数）の状態Ｓ（Ｓは０以上の整数）に向かうパスに対応するブランチラベルと、複数の受信信号系列とを用いて前記状態Ｓにおけるブランチメトリックを算出し、
前記時点Ｎの状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスメトリックに前記時点Ｎの前記状態Ｓにおけるブランチメトリックを加算して、前記時点Ｎの前記状態Ｓにおけるパスメトリックを算出し、
算出された複数の前記パスメトリックのうち、Ｌ（Ｌは１以上の整数）個のパスメトリックに対応するパスラベルを格納し、
前記時点Ｎの前記状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスラベルに、前記ブランチラベルを結合して前記時点Ｎの前記状態Ｓにおけるパスラベルを生成し、
前記トレリス線図における終点において選択されたＬ個のパスメトリックに対応するパスラベルを送信信号系列として出力することをコンピュータに実行させるプログラムが格納された非一時的なコンピュータ可読媒体。
【請求項１２】
ビタビアルゴリズムを用いて１つの受信信号系列から算出された複数の送信信号系列のうち、尤度の高い順にＬ（Ｌは１以上の整数）個の送信信号系列を選択し、
Ｍ（Ｍは１以上の整数）個のリスト出力ビタビデコーダから出力されたＭ×Ｌ個の送信信号系列のうち、尤度の高い順に選択したＬ個の送信信号系列を出力することをコンピュータに実行させるプログラムが格納された非一時的なコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は復号装置、復号方法、及びプログラムに関する。
【背景技術】
【０００２】
ディジタルデータ通信システム及び記憶システムの運用において、様々な要因によって生じ得るビット誤りへの対策が施されている。なかでも代表的な技術として、冗長なデータを付加する事で、ビット誤りの訂正を可能にする誤り訂正符号化技術が知られている。【０００３】
誤り訂正符号化技術は、送信側で情報データに冗長データを付加して送信信号系列を生成する符号化（エンコード）処理と、受信側で受け取ったノイズを含む受信信号系列から送信信号系列を推定する復号（デコード）処理からなる。一般にエンコード処理よりもデコード処理の方が多くの計算を必要とし、その計算の効率化や実現手段が実用上の課題となることが多い。【０００４】
一般的なデコード処理方法として、ビタビアルゴリズムを用いたビタビデコーダが良く知られている。これは送信信号系列をトレリス線図と呼ばれるグラフの経路（パス）とみなし、与えられた受信系列に対して最も尤度の高いパスを効率的に選出する手段としてビタビアルゴリズムを利用する。ビタビデコーダは、ビタビアルゴリズムを利用することにより送信信号系列を推定する方法である。【０００５】
誤り訂正能力の向上のためのビタビデコーダの改良方法が幾つか知られている。特許文献２あるいは非特許文献１では、受信系列に対して最も尤度の高いパスを一つだけ選択するのではなく、尤度の高い方から予め定められた複数個のパスを選択して出力する、リスト出力ビタビデコーダが開示されている。また特許文献３では、尤度の高いパスを出力するのではなく、そのパスの定める送信信号系列の各ビットに関する信頼度（事後確率）を算出し、出力する軟出力ビタビデコーダが開示されている。これらはいずれも、特許文献１に提示されているような、複数の誤り訂正符号を組み合わせて使用する連接符号化方式に関するデコード処理方法として有用である事が知られている。【０００６】
さらに、特許文献４には、複数の送信アンテナ及び複数の受信アンテナを有するＭＩＭＯ（Multiple-Input Multiple-Output）伝送系におけるビタビ復号器の構成が開示されている。特許文献４に開示されているビタビ復号器は、複数の受信アンテナから受け取った一つの受信信号系列から送信信号系列を算出する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】米国特許第５４４６７４７号
【特許文献２】米国特許第５５３７４４４号
【特許文献３】米国特許第５９３３４６２号
【特許文献４】特開２０１１−２３９１０７号公報
【非特許文献】
【０００８】
【非特許文献１】N. Seshadri and C.-E. W. Sundberg, “List Viterbi decoding algorithms with applications,” IEEE Transactions on Communications, vol.42, no.2/3/4, Feb./Mar./Apr. 1994.
【非特許文献２】E. Arikan, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,” IEEE Transactions on Information Theory, vol.55, no.7, pp.3051-3073, July 2009.
【非特許文献３】I. Tal and A. Vardy, “List decoding of polar codes,” IEEE Transactions on Information Theory, vpl.61, no.5, pp.2213-2226, May 2015.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
このように、一般的なビタビデコーダ及びその改良は、いずれも与えられた一つの受信信号系列に対して、それに対応する送信信号系列、あるいは送信信号系列の候補となるリスト、あるいは信頼度を算出する。つまり、一般的なビタビデコーダ及びその改良は、与えられた一つの受信信号系列に対応する送信信号系列に関する情報量を増やすことによって、デコード処理結果の精度を向上させることを目指している。この技術の発展形として、入力である受信信号系列が複数与えられた場合に、そのいずれかに対して尤度の高い送信信号系列のリストを算出することが求められている。【００１０】
本開示の１つの目的は、入力である受信信号系列が複数与えられた時に、そのいずれかに対して尤度の高い送信信号系列のリストを算出することができる復号装置、復号方法、及びプログラムを提供することにある。
【課題を解決するための手段】
【００１１】
本開示の第１の態様にかかる復号装置は、トレリス線図における時点Ｎ（Ｎは０以上の整数）の状態Ｓ（Ｓは０以上の整数）に向かうパスに対応するブランチラベルと、複数の受信信号系列とを用いて前記状態Ｓにおけるブランチメトリックを算出する多入力ブランチメトリック計算ユニットと、前記時点Ｎの状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスメトリックに前記時点Ｎの前記状態Ｓにおけるブランチメトリックを加算して、前記時点Ｎの前記状態Ｓにおけるパスメトリックを算出するパスメトリック計算ユニットと、算出された複数の前記パスメトリックのうち、Ｌ（Ｌは１以上の整数）個のパスメトリックに対応するパスラベルを格納する生き残りパスリストメモリと、を備え、前記パスメトリック計算ユニットは、前記時点Ｎの前記状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスラベルに、前記ブランチラベルを結合して前記時点Ｎの前記状態Ｓにおけるパスラベルを生成し、前記生き残りパスリストメモリは、前記トレリス線図における終点において選択されたＬ個のパスメトリックに対応するパスラベルを送信信号系列として出力する。【００１２】
本開示の第２の態様にかかる復号方法は、トレリス線図における時点Ｎ（Ｎは０以上の整数）の状態Ｓ（Ｓは０以上の整数）に向かうパスに対応するブランチラベルと、複数の受信信号系列とを用いて前記状態Ｓにおけるブランチメトリックを算出し、前記時点Ｎの状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスメトリックに前記時点Ｎの前記状態Ｓにおけるブランチメトリックを加算して、前記時点Ｎの前記状態Ｓにおけるパスメトリックを算出し、算出された複数の前記パスメトリックのうち、Ｌ（Ｌは１以上の整数）個のパスメトリックに対応するパスラベルを格納し、前記時点Ｎの前記状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスラベルに、前記ブランチラベルを結合して前記時点Ｎの前記状態Ｓにおけるパスラベルを生成し、前記トレリス線図における終点において選択されたＬ個のパスメトリックに対応するパスラベルを送信信号系列として出力する。【００１３】
本開示の第３の態様にかかるプログラムは、トレリス線図における時点Ｎ（Ｎは０以上の整数）の状態Ｓ（Ｓは０以上の整数）に向かうパスに対応するブランチラベルと、複数の受信信号系列とを用いて前記状態Ｓにおけるブランチメトリックを算出し、前記時点Ｎの状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスメトリックに前記時点Ｎの前記状態Ｓにおけるブランチメトリックを加算して、前記時点Ｎの前記状態Ｓにおけるパスメトリックを算出し、算出された複数の前記パスメトリックのうち、Ｌ（Ｌは１以上の整数）個のパスメトリックに対応するパスラベルを格納し、前記時点Ｎの前記状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスラベルに、前記ブランチラベルを結合して前記時点Ｎの前記状態Ｓにおけるパスラベルを生成し、前記トレリス線図における終点において選択されたＬ個のパスメトリックに対応するパスラベルを送信信号系列として出力することをコンピュータに実行させる。
【発明の効果】
【００１４】
本開示により、入力である受信信号系列が複数与えられた時に、そのいずれかに対して尤度の高い送信信号系列のリストを算出することができる復号装置、復号方法、及びプログラムを提供するができる。
【図面の簡単な説明】
【００１５】
【図１】実施の形態２にかかる多入力・リスト出力ビタビデコード方法のフローチャートを示す図である。
【図２】実施の形態２にかかるトレリス線図の一例を示す図である。
【図３】実施の形態２にかかる多入力・リスト出力ビタビデコーダの構成図である。
【図４】実施の形態３にかかる多入力・リスト出力ビタビデコード方法のフローチャートを示す図である。
【図５】実施の形態３にかかる多入力・リスト出力ビタビデコーダの構成図である。
【図６】実施の形態４にかかるデコーダの構成図である。
【図７】実施の形態４にかかるPolar符号のリストデコーダを用いてデコード処理した誤り率特性を示す図である。
【図８】実施の形態２にかかる多入力・リスト出力ビタビデコーダの具体的な動作を示す図である。
【図９】実施の形態２にかかる生き残りパスを示す図である。
【図１０】実施の形態１にかかる復号装置の構成図である。
【図１１】それぞれの実施の形態にかかるデコーダの構成図である。
【発明を実施するための形態】
【００１６】
（実施の形態１）
以下、図面を参照して本開示の実施の形態について説明する。はじめに、図１０を用いて実施の形態１にかかる復号装置１０の構成図について説明する。復号装置１０は、プロセッサがメモリに格納されたプログラムを実行することによって動作するコンピュータ装置であってもよい。復号装置１０は、多入力ブランチメトリック計算ユニット１１、パスメトリック計算ユニット１２、及び生き残りパスリストメモリ１３を有している。多入力ブランチメトリック計算ユニット１１、パスメトリック計算ユニット１２、及び生き残りパスリストメモリ１３は、プロセッサがメモリに格納されたプログラムを実行することによって処理が実行されるソフトウェアもしくはモジュールであってもよい。または、多入力ブランチメトリック計算ユニット１１、パスメトリック計算ユニット１２、及び生き残りパスリストメモリ１３は、回路もしくはチップ等のハードウェアであってもよい。
【００１７】
多入力ブランチメトリック計算ユニット１１は、トレリス線図における時点Ｎ（Ｎは０以上の整数）の状態Ｓ（Ｓは０以上の整数）に向かうパスに対応するブランチラベルと、複数の受信信号系列とを用いて時点Ｎの状態Ｓにおけるブランチメトリックを算出する。ブランチラベルは、例えば、ビット列を用いて示される。ブランチメトリックは、受信信号系列と、ブランチラベルとの間の距離を示す。ブランチメトリックの数値が小さいほど、受信信号系列に対するブランチラベルの尤度が高い。
【００１８】
パスメトリック計算ユニット１２は、時点Ｎの状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスメトリックに、時点Ｎの状態Ｓにおけるブランチメトリックを加算して、時点Ｎの状態Ｓにおけるパスメトリックを算出する。つまり、パスメトリックは、ブランチメトリックの累積加算として示される。
【００１９】
さらに、パスメトリック計算ユニット１２は、時点Ｎの状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスラベルに、ブランチラベルを結合して時点Ｎの状態Ｓにおけるパスラベルを生成する。パスラベルは、時点０から時点Ｎまでに経由したパスに関連付けられたブランチラベルが結合された値である。パスラベルは、送信信号系列と言い換えられてもよい。
【００２０】
生き残りパスリストメモリ１３は、算出された複数のパスメトリックのうち、Ｌ（Ｌは１以上の整数）個のパスメトリックに対応するパスラベルを格納する。さらに、生き残りパスリストメモリ１３は、トレリス線図における終点において選択されたＬ個のパスメトリックに対応するパスラベルを送信信号系列として出力する。また、生き残りパスリストメモリ１３は、算出された複数のパスメトリックのうち、値の小さい順にＬ個のパスメトリックに対応するパスラベルを格納してもよい。
【００２１】
トレリス線図の終点においては、少なくとも１つの状態が存在する。生き残りパスリストメモリ１３は、トレリス線図における終点に存在する少なくとも１つの状態へ向かうパスに対応付けられたＬ個のパスメトリックに対応するパスラベルを格納する。
【００２２】
以上説明したように、図１０の復号装置１０は、複数の受信信号系列のいずれかに対して尤度の高いＬ個の送信信号系列を算出することができる。尤度の高いＬ個の送信信号系列は、送信信号系列のリストとして出力される。
【００２３】
（実施の形態２）
続いて、図１を用いて実施の形態２にかかる復号装置が実行する、多入力・リスト出力ビタビデコード方法のフローチャートについて説明する。
【００２４】
図１のフローチャートは、初期設定方法（１０１）、逐次演算方法（１０２）、終結方法（１０３）からなる。復号装置が図１のフローチャートを実行するにあたり、入力として、Ｍ個の長さＮの受信信号系列が与えられている（Ｍは２以上の整数；Ｎは正数）。Ｍ個の長さＮの受信信号系列をr0N-1(m)=(r0(m),r1(m),…,rN-1(m)), m=0,1,…,M-1、と記す。また、図１の出力するＬ個の送信信号系列をc0N-1(l,0), l=0,1,…,L-1と記す。これらは、r0N-1(m), m=0,1,…,M-1のいずれかに対して尤度の高いＬ個の送信信号系列のリストとなる。図１のフローチャート中に示したφt(l,i)とc0t-1(l,i)とは、各々時点ｔ、状態iにおけるl番目の生き残りパスに関するパスメトリックとパスラベルとを表す。mt-1(l,i)は、受信信号系列を指定するインデックスを表し、パスメトリックφt(l,i)が、パスラベルc0t-1(l,i)と受信信号系列r0t-1(mt-1(l,i))によって算出される事を意味する。パスメトリックの算出方法については後述する。
【００２５】
図２は、トレリス線図の一例を示す。黒丸で示したノードは状態を表す。始点の０から終点のＮまでＮ＋１個の時点があり(図２横方向）、各状態は時点毎に分類される。図２においては、各時点にＳ個の状態がある。トレリス線図において、時点ｔの状態iと時点ｔ＋１の状態jとの間に枝がある場合、その枝にはビット列が割り当てられており、これをブランチラベルと呼んでct[i;j]と記す。
【００２６】
受信信号rt(m)とブランチラベルct[i;j]との間のブランチメトリックをλt(m)[i;j]と記す。ブランチメトリックの算出方法の一例を次に示す。ブランチラベルct[i;j]をＢビットのデータb0,b1,…,bB-1とすると、受信信号rt(m)は、Ｂ個の実数値y0,y1,…,yB-1で表現できる。この時ブランチメトリックλt(m)[i;j]は、次の式１によって定まる。
【００２７】
【数１】
2019234903.tif 000003
・・・（式１）
【００２８】
式１において、δ(bk,yk)は、bk=1かつyk<0、あるいはbk=0かつyk≧0の時に０となり、それ以外のケースでは１となる関数とする。このブランチメトリックは、受信信号と送信ビット列との間の距離を表しており、ブランチメトリックの数値が小さい方が、受信信号に対するブランチラベルの尤度が高いと言える。尚、時点ｔの状態iと時点ｔ＋１の状態jとの間に枝が無い場合には、λt(m)[i;j]=∞とする。図１中では式１の右辺をd(rt(m),ct[i;j])と記述している。
【００２９】
パスメトリックは、ブランチメトリックの累積加算である。パスラベルは、ブランチラベルの系列、即ち送信信号系列である。従って、パスメトリックは、受信信号系列と送信信号系列との間の距離を表す数値となり、パスメトリックが小さい方ほど尤度が高いと言える。
【００３０】
図３は本開示の多入力・リスト出力ビタビデコーダの一構成例を示すブロック図である。図３の多入力・リスト出力ビタビデコーダは、Ｍ個の受信信号系列の各々から式１に例示したブランチメトリックを算出する多入力ブランチメトリック計算ユニット３０１を備える。さらに、多入力・リスト出力ビタビデコーダは、パスメトリックを計算するためのパスメトリック計算ユニット３０２を備える。さらに、多入力・リスト出力ビタビデコーダは、生き残りパスのパスメトリックを保存するパスメトリックメモリ３０３を備える。さらに、多入力・リスト出力ビタビデコーダは、生き残りパスに対応する受信信号系列のインデックスを保存するインデックスメモリ３０４を備える。インデックスメモリ３０４は、さらに多入力ブランチメトリック計算ユニット３０１の出力からパスメトリックの計算に必要なブランチメトリックを選択するセレクタ３０６の選択信号を生成する。さらに、多入力・リスト出力ビタビデコーダは、生き残りパスのリストを保存する生き残りパスリストメモリ３０５を備える。
【００３１】
［動作の説明］
次に実施形態２に係る図１の動作について図２のトレリス線図を用いて説明する。多入力・リスト出力ビタビデコーダへの入力として、Ｍ個の長さＮの受信信号系列
r0N-1(m), m=0,1,…,M-1、が与えられる。簡単のため、出力する送信信号系列のリストサイズＬに対して、Ｍ≦Ｌとする。
【００３２】
図１の初期設定方法（１０１）において、多入力ブランチメトリック計算ユニット３０１は、図２の時点０におけるパスメトリックの初期値と、パスメトリックに対応する受信信号系列を指定するインデックスの初期値とを設定する。前述の様にφ0(l,0)は、時点０、状態０におけるl番目のパスメトリックを表し、l=0,1,…,M-1に関して、予め設定された初期値μlに指定する。以下では簡単のため、初期値を０として説明する。また、これ以外の時点０におけるパスメトリックφ0(l,j)には最大の数値（∞と表記する）を割り当てておく。また、割りあてたパスメトリックに対する受信信号系列のインデックスをm0(l,j)=l, 0≦l<L, 0≦j<Sと指定する。尚、j=0以外のm0(l,j)については、任意の値で構わない。
【００３３】
逐次演算方法（１０２）において、多入力ブランチメトリック計算ユニット３０１は、時点ｔの生き残りパスのパスラベル等を用いて、時点ｔ＋１の生き残りパスラベル等を算出する。生き残りパスのパスラベル等は、生き残りパスのパスラベル、パスメトリック、及びパスメトリック算出のための受信信号系列を指定するインデックスを含む。
【００３４】
多入力ブランチメトリック計算ユニット３０１は、はじめに、受信信号rt(m)と、時点ｔの状態iと時点ｔ＋１の状態jとの間のブランチラベルct[i;j]と、式１とを用いてブランチメトリックλt(m)[i;j]を算出する。ブランチメトリックの算出は、かかわる全ての0≦m<M, 0≦i,j<Sについて行うこととする。
【００３５】
次に、ブランチメトリックを用いて、時点ｔ＋１の各状態jに関する生き残りパスに関するパスメトリックを算出する方法について説明する。時点ｔの状態iにおける生き残りパスのパスメトリックと前記のブランチメトリックを使用した次の式２に示した計算を、すべての0≦k<L, 0≦i<Sについて行う。
【００３６】
【数２】
2019234903.tif 000004
・・・（式２）
【００３７】
ここで、mt(k,i)は、パスメトリックφt(k,i)の算出に係わる受信信号系列を指定するインデックである。従って、式２は、時点tの状態iを経由して、時点ｔ＋１の状態jに到達するパスのパスメトリックとなる。すべての0≦k<L, 0≦i<Sに渡って、式２の値を算出し、この中で小さい方からl番目のパスメトリックを(0≦l<L)、時点ｔ＋１の状態jのl番目の生き残りパスのパスメトリックとして、φt+1(l,j)と記す。式２において、φt+1(l,j)を与えるkとiの組を各々k*及びi*記すと、パスメトリックφt+1(l,j)の算出にかかわる受信信号系列のインデックスmt+1(l,j)はmt(k*,i*)となる。尚、図１中のmin(l)はl番目に小さい事を意味し、argmin(l)はl番目に小さい値をとる定義域の値（kとiとの組）を意味する。
【００３８】
時点ｔ＋１の状態jのl番目の生き残りパスを表すパスラベルは、c0t(l,j)と表される。c0t(l,j)は、前記のk*及びi*によって、時点ｔの状態i*におけるk*番目の生き残りパスのパスラベルc0t-1(k*,i*)に、時点tの状態i*と時点ｔ＋１の状態jとの間のブランチラベルct[i*;j]を結合したとして表記される。逐次演算方法（１０２）は、以上の処理を時点１から時点Ｎ−１までの間、繰り返し行う。
【００３９】
終結方法（１０３）は終点Ｎにおける生き残りパスのパスラベル、パスメトリック、及び、パスメトリック算出のための受信信号系列を指定するインデックスを算出する。終点においては状態０以外に枝が無いため、状態０に到達するパスのみを考慮する点を除いて、その動作は逐次計算方法（１０２）と同様である。以上の方法によって、与えられたＭ個の長さＮの受信信号系列r0N-1(m), m=0,1,…,M-1、について、そのいずれかに対して尤度の大きいＬ個の送信信号系列c0N-1(l,0), l=0,1,…,L-1を算出する。
【００４０】
図３に示した多入力・リスト出力ビタビデコーダの動作は、図１のフローチャートにおいて説明した動作と同様である。多入力ブランチメトリック計算ユニット３０１は、図１の逐次演算方法（１０２）及び終結方法（１０３）における前記ブランチメトリックλt(m)[i;j] を算出する。多入力ブランチメトリック計算ユニット３０１において算出されたブランチメトリックは、セレクタ３０６を介してパスメトリック計算ユニット３０２へ出力される。パスメトリック計算ユニット３０２は、式２を用いてパスメトリックを算出する。尚、式２におけるパスメトリックφt(k,i)は、パスメトリックメモリ３０３に保持されている。インデックスmt(k,i)は、インデックスメモリ３０４に保持されている。パスメトリック計算ユニット３０２は、セレクタ３０６を介して受け取ったmt(k,i)の指定するブランチメトリックをφt(k,i)に加算する。図１において説明した動作と同様に、新たに選出されたパスメトリックφt+1(l,j)は、パスメトリックメモリ３０３に格納される。インデックスmt+1(l,j)は、インデックスメモリ３０４に格納される。パスラベルc0t-1(l,j)は、生き残りパスリストメモリ３０５に格納される。
【００４１】
[具体的な動作例]
続いて、図８を用いて、図３に示した多入力・リスト出力ビタビデコーダの具体的な動作例について説明する。図８は、具体的な動作を説明する際に使用するトレリス線図を示している。図８のトレリス線図は、時点数Ｎ＋１＝５、状態数Ｓ＝４である。図８のトレリス線図における各ブランチには４ビットのブランチラベルが割り当てられている。入力となる受信信号系列の数をＭ＝４として、各受信信号系列r03(m), m=0,1,2,3が次の様に与えられた場合について説明する。
r0(0)=(-4.26,-0.35,+0.47,+2.16), r1(0)=(-1.73,-0.17,+1.84,+0.94)
r2(0)=(+0.42,+2.69,-4.89,-1.26), r3(0)=(+1.85,+2.03,+0.04,-2.59)
r0(1)=(-4.26,-0.35,+0.47,+2.16), r1(1)=(-0.10,+2.01,-0.75,+0.27)
r2(1)=(+0.42,+2.69,-4.89,-1.26), r3(1)=(+0.06,-2.76,-1.12,+2.05)
r0(2)=(-0.58,+0.06,-1.80,-0.48), r1(2)=(-0.10,+2.01,-0.75,+0.27)
r2(2)=(+0.42,+2.69,-4.89,-1.26), r3(2)=(+1.85,+2.03,+0.04,-2.59)
r0(3)=(-0.58,+0.06,-1.80,-0.48), r1(3)=(-1.73,-0.17,+1.84,+0.94)
r2(3)=(+0.42,+2.69,-4.89,-1.26), r3(3)=(+0.06,-2.76,-1.12,+2.05)
【００４２】
パスメトリックと受信信号系列を指定するインデックスの初期値とを図１中の初期設定方法（１０１）にあるように設定する。尚、ここではパスメトリックの初期値を各々μ0=6.13, μ1=8.90, μ2=11.01, μ3=11.62とする。以下、時点及び状態毎に計算過程を示す。
【００４３】
図８は、時点０−１間のブランチラベルが全部で４パターン(0000,1111,0011,1100)あることを示している。合計１６個のブランチメトリックは、式１に従って以下の様に計算できる。
λ0(0)[0,0]=4.61, λ0(0)[0,1]=2.63, λ0(0)[0,2]=7.24, λ0(0)[0,3]=0.00
λ0(1)[0,0]=4.61, λ0(1)[0,1]=2.63, λ0(1)[0,2]=7.24, λ0(1)[0,3]=0.00
λ0(2)[0,0]=2.86, λ0(2)[0,1]=0.06, λ0(2)[0,2]=0.58, λ0(2)[0,3]=2.34
λ0(3)[0,0]=2.86, λ0(3)[0,1]=0.06, λ0(3)[0,2]=0.58, λ0(3)[0,3]=2.34
【００４４】
時点ｔ＝１の状態0,1,2,3における生き残りパスのパスメトリック、パスメトリックの算出に係わる受信信号系列を指定するインデックス、及び生き残りパスラベルを図１中逐次演算方法（１０２）に従って計算すると以下のようになる。
φ1(0,0)=10.74, m1(0,0)=0, c0(0,0)=0000
φ1(1,0)=13.51, m1(1,0)=1, c0(1,0)=0000
φ1(2,0)=13.87, m1(2,0)=2, c0(2,0)=0000
φ1(3,0)=14.48, m1(3,0)=3, c0(3,0)=0000
φ1(0,1)=8.76, m1(0,1)=0, c0(0,1)=1111
φ1(1,1)=11.07, m1(1,1)=2, c0(1,1)=1111
φ1(2,1)=11.53, m1(2,1)=1, c0(2,1)=1111
φ1(3,1)=11.68, m1(3,1)=3, c0(3,1)=1111
φ1(0,2)=11.59, m1(0,2)=2, c0(0,2)=0011
φ1(1,2)=12.20, m1(1,2)=3, c0(1,2)=0011
φ1(2,2)=13.37, m1(2,2)=0, c0(2,2)=0011
φ1(3,2)=16.14, m1(3,2)=1, c0(3,2)=0011
φ1(0,3)=6.13, m1(0,3)=0, c0(0,3)=1100
φ1(1,3)=8.90, m1(1,3)=1, c0(1,3)=1100
φ1(2,3)=13.35, m1(2,3)=2, c0(2,3)=1100
φ1(3,3)=13.96, m1(3,3)=3, c0(3,3)=1100
【００４５】
時点１−２間のブランチラベルも同様に全部で4パターン(0000,1111,0011,1100)あり、合計１６個のブランチメトリックは式１に従って計算できる。これを使って、時点ｔ＝２に関する各データは次の様に算出される。
φ2(0,0)=11.55, m2(0,0)=0, c01(0,0)=1111 1111
φ2(1,0)=12.64, m2(1,0)=0, c01(1,0)=0000 0000
φ2(2,0)=13.35, m2(2,0)=2, c01(2,0)=1111 1111
φ2(3,0)=13.81, m2(3,0)=1, c01(3,0)=1111 1111
φ2(0,1)=10.66, m2(0,1)=0, c01(0,1)=1111 0000
φ2(1,1)=11.92, m2(1,1)=2, c01(1,1)=1111 0000
φ2(2,1)=12.38, m2(2,1)=1, c01(2,1)=1111 0000
φ2(3,1)=13.52, m2(3,1)=0, c01(3,1)=0000 1111
φ2(0,2)=6.13, m2(0,2)=0, c01(0,2)=1100 1100
φ2(1,2)=11.66, m2(1,2)=1, c01(1,2)=1100 1100
φ2(2,2)=11.96, m2(2,2)=2, c01(2,2)=0011 0011
φ2(3,2)=13.97, m2(3,2)=3, c01(3,2)=1100 1100
φ2(0,3)=9.27, m2(0,3)=1, c01(0,3)=1100 0011
φ2(1,3)=10.81, m2(1,3)=0, c01(1,3)=1100 0011
φ2(2,3)=12.20, m2(2,3)=3, c01(2,3)=0011 1100
φ2(3,3)=13.37, m2(3,3)=0, c01(3,3)=0011 1100
【００４６】
時点２−３間のブランチラベルも同様に計算でき、これを使って、時点ｔ＝３に関する各データは次の様に算出される。
φ3(0,0)=13.77, m3(0,0)=0, c02(0,0)=1111 0000 1111
φ3(1,0)=15.03, m3(1,0)=2, c02(1,0)=1111 0000 1111
φ3(2,0)=15.49, m3(2,0)=1, c02(2,0)=1111 0000 1111
φ3(3,0)=16.63, m3(3,0)=0, c02(3,0)=0000 1111 1111
φ3(0,1)=14.66, m3(0,1)=0, c02(0,1)=1111 1111 1111
φ3(1,1)=15.75, m3(1,1)=0, c02(1,1)=0000 0000 1111
φ3(2,1)=16.46, m3(2,1)=2, c02(2,1)=1111 1111 1111
φ3(3,1)=16.81, m3(3,1)=0, c02(3,1)=1111 0000 0000
φ3(0,2)=6.13, m3(0,2)=0, c02(0,2)=1100 1100 0011
φ3(1,2)=11.66, m3(1,2)=1, c02(1,2)=1100 1100 0011
φ3(2,2)=11.96, m3(2,2)=2, c02(2,2)=0011 0011 0011
φ3(3,2)=13.97, m3(3,2)=3, c02(3,2)=1100 1100 0011
φ3(0,3)=9.27, m3(0,3)=1, c02(0,3)=1100 0011 0011
φ3(1,3)=10.81, m3(1,3)=0, c02(1,3)=1100 0011 0011
φ3(2,3)=12.20, m3(2,3)=3, c02(2,3)=0011 1100 0011
φ3(3,3)=13.37, m3(3,3)=0, c02(3,3)=0011 1100 0011
【００４７】
次の時点３−４間のブランチラベルの計算も同様である。これを用いて、終点ｔ＝４における唯一の状態０における生き残りパスのパスメトリック、パスメトリックの算出に係わる受信信号系列を指定するインデックス、及び生き残りパスラベルを図１中終結方法（１０３）に従って計算すると以下のようになる。
φ4(0,0)=6.17, m4(0,0)=0, c03(0,0)=1100 1100 0011 0011
φ4(1,0)=10.45, m4(1,0)=1, c03(1,0)=1100 0011 0011 1100
φ4(2,0)=12.00, m4(2,0)=2, c03(2,0)=0011 0011 0011 0011
φ4(3,0)=13.38, m4(3,0)=3, c03(3,0)=0011 1100 0011 1100
【００４８】
図９は、図８のトレリス線図の終点における４つの生き残りパスを示す。実線がc03(0,0)、破線がc03(1,0)、一点鎖線がc03(2,0)、二点鎖線がc03(3,0)の１６ビット系列に対応する。これらが前記の与えられた４つの受信信号系列r03(m), m=0,1,2,3のいずれかに対して尤度の高い（メトリックの小さい）４つの送信信号系列となる。尚、この例においては、与えられた４つの受信信号系列の各々について、最も尤度の高い送信信号系列が１つずつ選択されている。しかし、一般にはこのようになる保証はなく、一つの受信信号系列に対して尤度の高い４つの送信信号系列が選択される場合もある。
【００４９】
以上説明したように、図３に示す多入力・リスト出力ビタビデコーダは、複数の受信信号系列のいずれかに対して尤度の高い複数の送信信号系列を算出することができる。
【００５０】
（実施の形態３）
続いて、図４を用いて実施の形態３にかかる復号装置が実行する、多入力・リスト出力ビタビデコード方法のフローチャートについて説明する。
【００５１】
図４は実施の形態３に係る多入力・リスト出力ビタビデコード方法のフローチャートを示す。図４のフローチャートは、リスト出力ビタビデコード方法（４０１）と選択方法（４０２）とからなる。リスト出力ビタビデコード方法（４０１）は、与えられた単一の受信信号系列に対して尤度の高いＬ個の送信信号系列のリストを出力する。選択方法（４０２）は、Ｍ×Ｌ個の送信信号系列から尤度の大きい方からＬ個の送信信号系列を選択する。
【００５２】
図５は実施の形態３にかかる多入力・リスト出力ビタビデコーダの一構成例を示すブロック図である。多入力・リスト出力ビタビデコーダは、複数のリスト出力ビタビデコーダ５０１と、選択装置５０２とを有する。図５の多入力・リスト出力ビタビデコーダは、与えられた単一の受信信号系列に対して尤度の高いＬ個の送信信号系列のリストを出力する、リスト出力ビタビデコーダ５０１をＭ個備える。さらに、図５の多入力・リスト出力ビタビデコーダは、これらのリスト出力ビタビデコーダ５０１が出力する合計Ｍ×Ｌ個の送信信号系列から、尤度の大きい方からＬ個の送信信号系列を選択する選択装置５０２を備える。
【００５３】
続いて、図４に示した多入力・リスト出力ビタビデコード方法を説明する。図１と同様に、多入力・リスト出力ビタビデコーダに対する入力として、Ｍ個の長さＮの受信信号系列r0N-1(m), m=0,1,…,M-1が与えられる。
【００５４】
リスト出力ビタビデコーダ５０１は、各受信信号系列r0N-1(m)に対して、リスト出力ビタビデコード方法（４０１）を使用して、最も尤度の高い方からＬ個の送信信号系列c0N-1(l,m), l=0,1,…,L-1を選出する。多入力・リスト出力ビタビデコーダは、Ｍ個のリスト出力ビタビデコーダ５０１を用いて、リスト出力ビタビデコード方法（４０１）をＭ回実行する。その結果、合計のべＭ×Ｌ個の送信信号系列が得られる。
【００５５】
次いで、選択方法（４０２）において、選択装置５０２は、前記Ｍ×Ｌ個の送信信号系列の中から、尤度の最も大きいＬ個の送信信号系列c0N-1(l), l=0,1,…,L-1を選択する。具体的には、選択装置５０２は、リスト出力ビタビデコード方法（４０１）においてＬ個の送信信号系列の選出に用いた尤度情報（メトリック）を使用して、Ｌ個の送信信号系列を選択する。
【００５６】
図５に示した実施の形態３にかかる多入力・リスト出力ビタビデコーダの動作は、図４の多入力・リスト出力ビタビデコード方法と同様である。
【００５７】
以上説明したように、図５の多入力・リスト出力ビタビデコーダの出力は、与えられたＭ個の受信信号系列のいずれかに対して尤度の最も大きい送信信号系列からＬ個の送信信号系列を算出することができる。また、図４及び図５を用いて説明した、多入力・リスト出力ビタビデコーダの出力は、図８を用いて説明した多入力・リスト出力ビタビデコーダの出力結果と同様となる。
【００５８】
ここで、図５の多入力・リスト出力ビタビデコーダは、単一のリストビタビデコード方式のＭ倍相当の計算量と装置規模が必要となる。
【００５９】
一方、実施の形態２において説明した図３の多入力・リスト出力ビタビデコーダは、単一のリストビタビデコード方式と同程度の計算量と装置規模とすることができる。しかし、図３の多入力・リスト出力ビタビデコーダは、与えられたＭ個の受信信号系列のいずれかについて、必ずしも最も尤度が高い方からＬ個の送信信号系列のリストを与えるとは限らないケースがある。これに対して、実施の形態３において説明した多入力・リスト出力ビタビデコーダの出力は、最も尤度が高い方からＬ個の送信信号系列のリストとなる。
【００６０】
（実施の形態４）
続いて、図６を用いて実施の形態４にかかるデコーダの構成例を説明する。図６は、長さＮ＝Ｎ１×Ｎ２ビットのPolar符号に関するリストサイズＬのデコーダの一構成例を示すブロック図である。リストデコード演算ユニット６０１は、長さＮ１のPolar符号のデコード処理を実行するSC（Successive Cancelation）ユニットをＬ個備える。また、図６のデコーダは、リストデコード演算ユニット６０１をＮ２個備える。
【００６１】
さらに、多入力・リスト出力ビタビデコーダ６０２は、与えられたＭ個（ＭはＬ以下の正数）の長さＮ２の受信信号系列に関して、そのいずれかに対して尤度の高いＬ個の送信信号系列のリストを出力する。多入力・リスト出力ビタビデコーダ６０２は、図３あるいは図５に示される多入力・リスト出力ビタビデコーダである。選択装置６０３は、多入力・リスト出力ビタビデコーダ６０２の出力リストから、一つの送信信号系列を選択する。
【００６２】
続いて、図６に示したPolar符号のリストデコーダの動作について説明する。リストデコーダは、Polar符号化された長さＮの送信信号系列に対する受信信号系列r0N-1を入力する。この長さＮの受信信号系列r0N-1は、Ｎ２個の長さＮ１の受信信号系列に分割されて、r0N1-1、rN12N1-1,…, rN-N1N-1 となる。分割された受信信号系列の各々は、長さＮ１のPolar符号に関するSuccessive Cancellation (SC) デコード処理を実行するSCユニットをＬ個有するリストデコード演算ユニット６０１へ入力される。
【００６３】
リストデコード演算ユニット６０１は、全部でＮ２個ある。Ｎ２個のリストデコード演算ユニット６０１には、０からＮ２−１の番号が付けられる。第ｋ番目のリストデコード演算ユニット６０１は、長さＮ１の受信信号系列rkN1(k+1)N1-1をSCアルゴリズムによって処理する。さらに、第ｋ番目のリストデコード演算ユニット６０１は、長さＮ１の送信ビット列の各々のビットに関する尤度情報の候補を先頭ビットから順次、Ｌパターン分rk(0),rk(1),…, rk(L-1),を出力する。
【００６４】
リストデコード演算ユニット６０１が演算を実行することによって、第i番目のビットに対して、前記Ｌパターン分の尤度情報の候補が得られたと仮定する（iはＮ１−１以下の整数）。k=0,1,…,Ｎ２−１の全てに渡って、Ｌパターン分の尤度情報を集めることによって、Ｌ個の長さＮ２の系列r0N2-1(m),m=0,1,…,L-1が得られる。これらをＬ個の受信信号系列とみなして、多入力・リスト出力ビタビデコーダ６０２は、Ｌ個の受信信号系列を受け取る。さらに、多入力・リスト出力ビタビデコーダ６０２は、Ｌ個の長さＮ２ビットの送信信号系列のリストc0N2-1(m),m=0,1,…,L-1を算出する。
【００６５】
これらの情報多入力・リスト出力ビタビデコーダ６０２は、ck(0),ck(1),…,ck(L-1)をＬパターン分の尤度情報rk(0),rk(1),…, rk(L-1)に対応する硬判定情報としてリストデコード演算ユニット６０１にフィードバックする。
【００６６】
リストデコード演算ユニット６０１は、硬判定情報のフィードバックを用いて、次の第i＋１番目のビットに関する尤度情報の候補を同様にＬパターン分算出する。以上を繰り返し、合計Ｎ１回の多入力・リスト出力ビタビデコーダの実行によって、多入力・リスト出力ビタビデコーダ６０２は、受信信号系列r0N-1に対するＬ個の送信ビット系列の候補uN-1(l), l=0,1,…,L-1を得ることができる。
【００６７】
選択装置６０３は、は送信ビット系列の候補uN-1(l), l=0,1,…,L-1から一つを選択して出力する。一例として、事前に送信ビットに誤り検出用のCRC（Cyclic Redundancy Check）ビットを入れておき、誤りが検出されなかった候補を選択する方法がある。
【００６８】
次に、図６に示したPolar符号のリストデコーダの処理ステップ数削減効果について具体例を挙げて説明する。例えば、Ｎ＝１０２４ビットのPolar符号をリストサイズＬ＝８でリストデコードする場合について説明する。図６のリストデコーダにおいて、Ｎ１＝６４、Ｎ２＝１６とすれば、リストデコード演算ユニット６０１が実行する処理ステップ数は、２Ｎ１−２＝１２６と概算される。Ｎ２＝１６の多入力・リスト出力ビタビデコーダに関しては、実施の形態２において示した様に、対応するトレリス線図が時点数４、ブランチラベル４ビット、状態数８以下で表現できる。そのため、１回辺りの処理ステップ数は４であり、これがＮ１回実行されるため、処理ステップ数は４×６４＝２５６となる。従って、図６に示したPolar符号のリストデコーダは、原理的には合計１２６＋２５６＝３８２のステップ数でリスト復号処理を行うことができる。一方、一般的なPolar符号のリストデコーダにおいて、長さＮ＝１０２４ビット、リストサイズ８のリストデコードユニットを用いて処理した場合のステップ数は２Ｎ−２＝２０４６であり、処理ステップ数は大幅に削減されている。
【００６９】
図７は、Ｎ＝１０２４ビットのPolar符号を図６の構成のPolar符号のリストデコーダ（リストサイズＬ＝８）を用いてデコード処理した誤り率特性を示している。多入力・リスト出力ビタビデコーダとして、図３の構成と図５の構成を用いた場合の差を示しているが図５の方が若干優るもののほとんど差がない事がわかる。
【００７０】
続いて以下では、図１１を用いて、上述の複数の実施形態で説明された図３、図５、及び図６における各種デコーダの構成例について説明する。図１１は、デコーダの構成例を示すブロック図である。図１１を参照すると、デコーダは、ネットワークインタフェース１１０、プロセッサ１１１、及びメモリ１１２を含む。ネットワークインタフェース１１０は、通信システムを構成する他のネットワークノード装置と通信するために使用される。ネットワークインタフェース１１０は、例えば、IEEE 802.3 seriesに準拠したネットワークインタフェースカード（NIC）を含んでもよい。
【００７１】
プロセッサ１１１は、メモリ１１２からソフトウェア（コンピュータプログラム）を読み出して実行することで、上述の実施形態においてフローチャートを用いて説明されたデコーダの処理を行う。プロセッサ１１１は、例えば、マイクロプロセッサ、MPU（Micro Processing Unit）、又はCPU（Central Processing Unit）であってもよい。プロセッサ１１１は、複数のプロセッサを含んでもよい。
【００７２】
メモリ１１２は、揮発性メモリ及び不揮発性メモリの組み合わせによって構成される。メモリ１１２は、プロセッサ１１１から離れて配置されたストレージを含んでもよい。この場合、プロセッサ１１１は、図示されていないI/Oインタフェースを介してメモリ１１２にアクセスしてもよい。
【００７３】
図１１の例では、メモリ１１２は、ソフトウェアモジュール群を格納するために使用される。プロセッサ１１１は、これらのソフトウェアモジュール群をメモリ１１２から読み出して実行することで、上述の実施形態において説明されたデコーダの処理を行うことができる。
【００７４】
図１１を用いて説明したように、デコーダが有するプロセッサの各々は、図面を用いて説明されたアルゴリズムをコンピュータに行わせるための命令群を含む１又は複数のプログラムを実行する。
【００７５】
上述の例において、プログラムは、様々なタイプの非一時的なコンピュータ可読媒体（non-transitory computer readable medium）を用いて格納され、コンピュータに供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記録媒体（tangible storage medium）を含む。非一時的なコンピュータ可読媒体の例は、磁気記録媒体、光磁気記録媒体、ＣＤ−ＲＯＭ（Read Only Memory）、ＣＤ−Ｒ、ＣＤ−Ｒ／Ｗ、半導体メモリを含む。磁気記録媒体は、例えば、フレキシブルディスク、磁気テープ、ハードディスクドライブであってもよい。光磁気記録媒体は、例えば、光磁気ディスクであってもよい。半導体メモリは、例えば、マスクＲＯＭ、ＰＲＯＭ（Programmable ROM）、ＥＰＲＯＭ（Erasable PROM）、フラッシュＲＯＭ、ＲＡＭ（Random Access Memory）であってもよい。また、プログラムは、様々なタイプの一時的なコンピュータ可読媒体（transitory computer readable medium）によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、プログラムをコンピュータに供給できる。
【００７６】
なお、本開示は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。
【００７７】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
（付記１）
トレリス線図における時点Ｎ（Ｎは０以上の整数）の状態Ｓ（Ｓは０以上の整数）に向かうパスに対応するブランチラベルと、複数の受信信号系列とを用いて前記状態Ｓにおけるブランチメトリックを算出する多入力ブランチメトリック計算ユニットと、
前記時点Ｎの状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスメトリックに前記時点Ｎの前記状態Ｓにおけるブランチメトリックを加算して、前記時点Ｎの前記状態Ｓにおけるパスメトリックを算出するパスメトリック計算ユニットと、
算出された複数の前記パスメトリックのうち、Ｌ（Ｌは１以上の整数）個のパスメトリックに対応するパスラベルを格納する生き残りパスリストメモリと、を備え、
前記パスメトリック計算ユニットは、
前記時点Ｎの前記状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスラベルに、前記ブランチラベルを結合して前記時点Ｎの前記状態Ｓにおけるパスラベルを生成し、
前記生き残りパスリストメモリは、
前記トレリス線図における終点において選択されたＬ個のパスメトリックに対応するパスラベルを送信信号系列として出力する、復号装置。
（付記２）
前記パスメトリックを算出する際に用いられた前記受信信号系列を指定するインデックスを格納するインデックスメモリをさらに備える、付記１に記載の復号装置。
（付記３）
算出された前記パスメトリックを格納するパスメトリックメモリをさらに備え、
前記パスメトリック計算ユニットは、
前記インデックスが示す前記受信信号系列を用いて算出された前記ブランチメトリックを、前記パスメトリックメモリに格納された前記時点Ｎ−１のそれぞれの状態におけるパスメトリックに加算する、付記２に記載の復号装置。
（付記４）
前記生き残りパスリストメモリは、
算出された複数の前記パスメトリックのうち、値の小さい順にＬ個のパスメトリックに対応するパスラベルを格納する、付記１乃至３のいずれか１項に記載の復号装置。
（付記５）
前記トレリス線図における終点は、状態数を１とし、
前記パスメトリック計算ユニットは、
前記トレリス線図における終点の１つの状態に向かうパスに対応するパスメトリックを算出し、さらに、パスラベルを生成する、付記１乃至４のいずれか１項に記載の復号装置。
（付記６）
長さＮ１（Ｎ１は１以上の整数）ビットのＰｏｌａｒ符号のデコード処理を実行し、リストサイズを１とするＳＣユニットをＬ個有する演算ユニットをさらに備え、
前記多入力ブランチメトリック計算ユニットは、
Ｎ２（Ｎ２は１以上の整数）個の前記演算ユニットから出力される長さＮ２ビットのＬ個の受信信号系列と前記ブランチラベルとを用いて前記ブランチメトリックを算出する、付記１乃至５のいずれか１項に記載の復号装置。
（付記７）
ビタビアルゴリズムを用いて１つの受信信号系列から算出された複数の送信信号系列のうち、尤度の高い順にＬ（Ｌは１以上の整数）個の送信信号系列を選択するリスト出力ビタビデコーダと、
Ｍ（Ｍは１以上の整数）個の前記リスト出力ビタビデコーダから出力されたＭ×Ｌ個の送信信号系列のうち、尤度の高い順に選択したＬ個の送信信号系列を出力する選択ユニットと、を備える復号装置。
（付記８）
長さＮ１（Ｎ１は１以上の整数）ビットのＰｏｌａｒ符号のデコード処理を実行し、リストサイズを１とするＳＣユニットをＬ個有する演算ユニットをさらに備え、
前記リスト出力ビタビデコーダは、
Ｎ２（Ｎ２は１以上の整数）個の前記演算ユニットから出力される長さＮ２ビットの受信信号系列から複数の送信信号系列を算出する、付記７に記載の復号装置。
（付記９）
トレリス線図における時点Ｎ（Ｎは０以上の整数）の状態Ｓ（Ｓは０以上の整数）に向かうパスに対応するブランチラベルと、複数の受信信号系列とを用いて前記状態Ｓにおけるブランチメトリックを算出し、
前記時点Ｎの状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスメトリックに前記時点Ｎの前記状態Ｓにおけるブランチメトリックを加算して、前記時点Ｎの前記状態Ｓにおけるパスメトリックを算出し、
算出された複数の前記パスメトリックのうち、Ｌ（Ｌは１以上の整数）個のパスメトリックに対応するパスラベルを格納し、
前記時点Ｎの前記状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスラベルに、前記ブランチラベルを結合して前記時点Ｎの前記状態Ｓにおけるパスラベルを生成し、
前記トレリス線図における終点において選択されたＬ個のパスメトリックに対応するパスラベルを送信信号系列として出力する、復号方法。
（付記１０）
ビタビアルゴリズムを用いて１つの受信信号系列から算出された複数の送信信号系列のうち、尤度の高い順にＬ（Ｌは１以上の整数）個の送信信号系列を選択し、
Ｍ（Ｍは１以上の整数）個のリスト出力ビタビデコーダから出力されたＭ×Ｌ個の送信信号系列のうち、尤度の高い順に選択したＬ個の送信信号系列を出力する、復号方法。
（付記１１）
トレリス線図における時点Ｎ（Ｎは０以上の整数）の状態Ｓ（Ｓは０以上の整数）に向かうパスに対応するブランチラベルと、複数の受信信号系列とを用いて前記状態Ｓにおけるブランチメトリックを算出し、
前記時点Ｎの状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスメトリックに前記時点Ｎの前記状態Ｓにおけるブランチメトリックを加算して、前記時点Ｎの前記状態Ｓにおけるパスメトリックを算出し、
算出された複数の前記パスメトリックのうち、Ｌ（Ｌは１以上の整数）個のパスメトリックに対応するパスラベルを格納し、
前記時点Ｎの前記状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスラベルに、前記ブランチラベルを結合して前記時点Ｎの前記状態Ｓにおけるパスラベルを生成し、
前記トレリス線図における終点において選択されたＬ個のパスメトリックに対応するパスラベルを送信信号系列として出力することをコンピュータに実行させるプログラム。
（付記１２）
ビタビアルゴリズムを用いて１つの受信信号系列から算出された複数の送信信号系列のうち、尤度の高い順にＬ（Ｌは１以上の整数）個の送信信号系列を選択し、
Ｍ（Ｍは１以上の整数）個のリスト出力ビタビデコーダから出力されたＭ×Ｌ個の送信信号系列のうち、尤度の高い順に選択したＬ個の送信信号系列を出力することをコンピュータに実行させるプログラム。
【符号の説明】
【００７８】
１０  復号装置
１１  多入力ブランチメトリック計算ユニット
１２  パスメトリック計算ユニット
１３  生き残りパスリストメモリ
１１０  ネットワークインタフェース
１１１  プロセッサ
１１２  メモリ
３０１  多入力ブランチメトリック計算ユニット
３０２  パスメトリック計算ユニット
３０３  パスメトリックメモリ
３０４  インデックスメモリ
３０５  生き残りパスリストメモリ
３０６  セレクタ
５０１  リスト出力ビタビデコーダ
５０２  選択装置
６０１  リストデコード演算ユニット
６０２  多入力・リスト出力ビタビデコーダ
６０３  選択装置
【図１】
2019234903.tif 000005
【図２】
2019234903.tif 000006
【図３】
2019234903.tif 000007
【図４】
2019234903.tif 000008
【図５】
2019234903.tif 000009
【図６】
2019234903.tif 000010
【図７】
2019234903.tif 000011
【図８】
2019234903.tif 000012
【図９】
2019234903.tif 000013
【図１０】
2019234903.tif 000014
【図１１】
2019234903.tif 000015
【手続補正書】
【提出日】令和2年11月24日(2020.11.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
トレリス線図における時点Ｎ（Ｎは０以上の整数）の状態Ｓ（Ｓは０以上の整数）に向かうパスに対応するブランチラベルと、複数の受信信号系列とを用いて前記状態Ｓにおけるブランチメトリックを算出する多入力ブランチメトリック計算手段と、
前記時点Ｎの状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスメトリックに前記時点Ｎの前記状態Ｓにおけるブランチメトリックを加算して、前記時点Ｎの前記状態Ｓにおけるパスメトリックを算出するパスメトリック計算手段と、
算出された複数の前記パスメトリックのうち、Ｌ（Ｌは１以上の整数）個のパスメトリックに対応するパスラベルを格納する生き残りパスリストメモリと、を備え、
前記パスメトリック計算手段は、
前記時点Ｎの前記状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスラベルに、前記ブランチラベルを結合して前記時点Ｎの前記状態Ｓにおけるパスラベルを生成し、
前記生き残りパスリストメモリは、
前記トレリス線図における終点において選択されたＬ個のパスメトリックに対応するパスラベルを送信信号系列として出力する、復号装置。
【請求項２】
前記パスメトリックを算出する際に用いられた前記受信信号系列を指定するインデックスを格納するインデックスメモリをさらに備える、請求項１に記載の復号装置。
【請求項３】
算出された前記パスメトリックを格納するパスメトリックメモリをさらに備え、
前記パスメトリック計算手段は、
前記インデックスが示す前記受信信号系列を用いて算出された前記ブランチメトリックを、前記パスメトリックメモリに格納された前記時点Ｎ−１のそれぞれの状態におけるパスメトリックに加算する、請求項２に記載の復号装置。
【請求項４】
前記生き残りパスリストメモリは、
算出された複数の前記パスメトリックのうち、値の小さい順にＬ個のパスメトリックに対応するパスラベルを格納する、請求項１乃至３のいずれか１項に記載の復号装置。
【請求項５】
前記トレリス線図における終点は、状態数を１とし、
前記パスメトリック計算手段は、
前記トレリス線図における終点の１つの状態に向かうパスに対応するパスメトリックを算出し、さらに、パスラベルを生成する、請求項１乃至４のいずれか１項に記載の復号装置。
【請求項６】
長さＮ１（Ｎ１は１以上の整数）ビットのＰｏｌａｒ符号のデコード処理を実行し、リストサイズを１とするＳＣユニットをＬ個有する演算手段をさらに備え、
前記多入力ブランチメトリック計算手段は、
Ｎ２（Ｎ２は１以上の整数）個の前記演算手段から出力される長さＮ２ビットのＬ個の受信信号系列と前記ブランチラベルとを用いて前記ブランチメトリックを算出する、請求項１乃至５のいずれか１項に記載の復号装置。
【請求項７】
ビタビアルゴリズムを用いて１つの受信信号系列から算出された複数の送信信号系列のうち、尤度の高い順にＬ（Ｌは１以上の整数）個の送信信号系列を選択するリスト出力ビタビデコーダと、
Ｍ（Ｍは１以上の整数）個の前記リスト出力ビタビデコーダから出力されたＭ×Ｌ個の送信信号系列のうち、尤度の高い順に選択したＬ個の送信信号系列を出力する選択手段と、を備える復号装置。
【請求項８】
長さＮ１（Ｎ１は１以上の整数）ビットのＰｏｌａｒ符号のデコード処理を実行し、リストサイズを１とするＳＣユニットをＬ個有する演算手段をさらに備え、
前記リスト出力ビタビデコーダは、
Ｎ２（Ｎ２は１以上の整数）個の前記演算手段から出力される長さＮ２ビットの受信信号系列から複数の送信信号系列を算出する、請求項７に記載の復号装置。
【請求項９】
トレリス線図における時点Ｎ（Ｎは０以上の整数）の状態Ｓ（Ｓは０以上の整数）に向かうパスに対応するブランチラベルと、複数の受信信号系列とを用いて前記状態Ｓにおけるブランチメトリックを算出し、
前記時点Ｎの状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスメトリックに前記時点Ｎの前記状態Ｓにおけるブランチメトリックを加算して、前記時点Ｎの前記状態Ｓにおけるパスメトリックを算出し、
算出された複数の前記パスメトリックのうち、Ｌ（Ｌは１以上の整数）個のパスメトリックに対応するパスラベルを格納し、
前記時点Ｎの前記状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスラベルに、前記ブランチラベルを結合して前記時点Ｎの前記状態Ｓにおけるパスラベルを生成し、
前記トレリス線図における終点において選択されたＬ個のパスメトリックに対応するパスラベルを送信信号系列として出力する、復号方法。
【請求項１０】
ビタビアルゴリズムを用いて１つの受信信号系列から算出された複数の送信信号系列のうち、尤度の高い順にＬ（Ｌは１以上の整数）個の送信信号系列を選択し、
Ｍ（Ｍは１以上の整数）個のリスト出力ビタビデコーダから出力されたＭ×Ｌ個の送信信号系列のうち、尤度の高い順に選択したＬ個の送信信号系列を出力する、復号方法。
【請求項１１】
トレリス線図における時点Ｎ（Ｎは０以上の整数）の状態Ｓ（Ｓは０以上の整数）に向かうパスに対応するブランチラベルと、複数の受信信号系列とを用いて前記状態Ｓにおけるブランチメトリックを算出し、
前記時点Ｎの状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスメトリックに前記時点Ｎの前記状態Ｓにおけるブランチメトリックを加算して、前記時点Ｎの前記状態Ｓにおけるパスメトリックを算出し、
算出された複数の前記パスメトリックのうち、Ｌ（Ｌは１以上の整数）個のパスメトリックに対応するパスラベルを格納し、
前記時点Ｎの前記状態Ｓとパスを形成する時点Ｎ−１のそれぞれの状態におけるパスラベルに、前記ブランチラベルを結合して前記時点Ｎの前記状態Ｓにおけるパスラベルを生成し、
前記トレリス線図における終点において選択されたＬ個のパスメトリックに対応するパスラベルを送信信号系列として出力することをコンピュータに実行させるプログラム。
【請求項１２】
ビタビアルゴリズムを用いて１つの受信信号系列から算出された複数の送信信号系列のうち、尤度の高い順にＬ（Ｌは１以上の整数）個の送信信号系列を選択し、
Ｍ（Ｍは１以上の整数）個のリスト出力ビタビデコーダから出力されたＭ×Ｌ個の送信信号系列のうち、尤度の高い順に選択したＬ個の送信信号系列を出力することをコンピュータに実行させるプログラム。
【国際調査報告】
2019234903.tif 000016
2019234903.tif 000017