(57)【要約】【課題】  本発明は、トレリス又はターボトレリス符号化変調方式において計算量を大幅に削減できる復号方法及び復号装置を提供する。【解決手段】  デコーダ１の２乗ユークリッド距離計算手段１１で受信信号に対して候補信号点をルックアップテーブルを参照して代表メトリックを特定して２乗ユークリッド距離を算出し、ブランチメトリック計算手段１２で２乗ユークリッド距離の符号を反転したブランチメトリックを計算し、前方パスメトリック計算手段１３で時系列のパスメトリックを計算し、それを硬判定ブロック２で硬判定して下位３ビットを求め、それと受信信号とによって上位ビットデコーダ３で上位ビットを復号するトレリス復号装置である。【選択図】        図４
2006173724.tif 000002
【特許請求の範囲】
【請求項１】
トレリス符号化変調方式における復号方法であって、
情報ビットの内、下位ｎビットを畳み込み符号化し、上位ビットは符号化せず、マッピングされて伝送される信号について、
復号装置が、前記下位ｎビットの情報ビットが共通で、前記上位ビットが異なる並列遷移が存在するものとして、当該並列遷移の内、受信信号との距離が最も小さい信号点に対応する遷移を並列遷移の代表遷移として置き換えるに際して、予め受信信号の受信領域から遠い信号点に対するブランチを代表ブランチから除外したテーブルを形成しておき、当該テーブルを参照して代表ブランチの候補信号点を特定し、並列遷移の代表遷移への置き換えによって前記下位ｎビットのみに関するトレリス線図に置き換えて、前記下位ｎビットの情報ビットとパリティビットを合わせた下位ｎ＋１ビットを、ビタビアルゴリズムを用いて復号することを特徴とする復号方法。
【請求項２】
ターボトレリス符号化変調方式における復号方法であって、
情報ビットの内、下位ｎビットをターボ符号化し、上位ビットは符号化せず、マッピングされて伝送される信号について、
復号装置が、前記下位ｎビットの情報ビットが共通で、前記上位ビットが異なる並列遷移が存在するものとして、当該並列遷移の内、受信信号との距離が最も小さい信号点に対応する遷移を並列遷移の代表遷移として置き換えることで、前記下位ｎビットのみに関するトレリス線図に置き換えて、前記下位ｎビットの情報ビットとパリティビットを合わせた下位ｎ＋１ビットを、 Max-log MAP アルゴリズムを用いた繰り返し復号により復号することを特徴とする復号方法。
【請求項３】
並列遷移の代表遷移へ置き換えは、予め受信信号の受信領域から遠い信号点に対するブランチを代表ブランチから除外したテーブルを形成しておき、当該テーブルを参照して代表ブランチの候補信号点を特定することで為されることを特徴とする請求項２記載の復号方法。
【請求項４】
下位ｎビットにおけるｎは、２又は３であることを特徴とする請求項１又は２記載の復号方法。
【請求項５】
受信領域は、受信信号の硬判定結果に対応する判定領域であり、テーブル参照には受信信号の硬判定結果と特定ビットの情報ビットとパリティビットをインデックスとすることを特徴とする請求項１又は３記載の復号方法。
【請求項６】
代表ブランチ選択の候補となる候補信号点をテーブルに設定するために、候補信号点を決定する処理は、代表ブランチ選択の比較対象となる全信号点の中で、判定領域との距離が最小になる信号点を代表ブランチの候補信号点とすることを特徴とする請求項５記載の復号方法。
【請求項７】
代表ブランチ選択の比較対象の信号点が複数ある場合に、各信号点を結ぶ線分に対する垂直２等分線が判定領域外を通れば、判定領域との距離が最小になる信号点を代表ブランチの候補信号点とし、前記垂直２等分線が判定領域内を通れば、結ばれた両点を代表ブランチの候補信号点とすることを特徴とする請求項６記載の復号方法。
【請求項８】
トレリス符号化変調方式における復号装置であって、
受信信号の硬判定結果の判定領域との距離が最小となる信号点を代表ブランチの候補信号点として記憶するルックアップテーブルを備え、入力される受信信号に対して前記ルックアップテーブルを参照し、代表ブランチの候補信号点を特定し、特定された候補信号点と受信信号の信号点との２乗ユークリッド距離を計算する２乗ユークリッド距離計算手段、計算された２乗ユークリッド距離の符号を反転したブランチメトリックを計算するブランチメトリック計算手段、ブランチメトリックを加算して得られるパスメトリックを算出するパスメトリック算出手段を備えるデコーダと、
前記パスメトリックを硬判定して情報ビットの下位ｎビットとパリティビットを合わせた送信シンボルの下位ｎ＋１ビットを得る硬判定ブロックと、
前記送信シンボルの下位ｎ＋１ビットと受信信号から上位ビットを復号する上位ビットデコーダとを有することを特徴とする復号装置。
【請求項９】
ターボトレリス符号化変調方式における復号装置であって、
第１のデコーダと、第２のデコーダと、第１の硬判定ブロックと、第２の硬判定ブロックと、インタリーバと、第１のデインタリーバと、第２のデインタリーバと、第１の加算器と、第２の加算器と、上位ビットデコーダとを備え、
前記第１のデコーダは、受信信号の硬判定結果の判定領域との距離が最小となる信号点を代表ブランチの候補信号点として記憶するルックアップテーブルを備え、前記ルックアップテーブルを参照して代表ブランチの候補信号点を特定して、Max-log MAPを基にした簡易復号アルゴリズムにより、前記第１のデインタリーバで系列順を戻した下位ｎ＋１ビットと受信信号を入力して復号し、
前記第１の加算器は、前記第１のデコーダからの出力と前記第１のデインタリーバからの出力の符号を反転したものを加算し、
前記インタリーバは、前記第１の加算器からの出力について情報の入れ替えを行い、前記第２の加算器と前記第２のデコーダに出力すると共に、受信信号について情報の入れ替えを行い、前記第２のデコーダに出力し、
前記第２のデコーダは、受信信号の硬判定結果の判定領域との距離が最小となる信号点を代表ブランチの候補信号点として記憶するルックアップテーブルを備え、前記ルックアップテーブルを参照して代表ブランチの候補信号点を特定して、Max-log MAPを基にした簡易復号アルゴリズムにより、前記インタリーバからの出力を復号し、
前記第２の加算器は、前記インタリーバからの出力の符号を反転したものと前記第２のデコーダからの出力を加算して前記第１のデインタリーバに出力し、
前記第１の硬判定ブロックは、前記第１のデコーダからの出力を硬判定してパリティビットを出力し、
前記第２の硬判定ブロックは、前記第２のデコーダからの出力を硬判定して情報ビットの下位ｎビットとパリティビットを出力し、
前記第２のデインタリーバは、前記第２の硬判定ブロックからの情報ビットの下位ｎビットとパリティビットについて系列順を戻して出力し、
前記上位ビットデコーダは、前記第２のデインタリーバからの情報ビットの下位ｎビットと前記第１の硬判定ブロックから出力されるパリティビット又は前記第２のデインタリーバから出力されるパリティビットを入力すると共に、受信信号を入力して上位ビットを復号するものであることを特徴とする復号装置。
【請求項１０】
下位ｎビットにおけるｎは、２又は３であることを特徴とする請求項８又は９記載の復号装置。
【請求項１１】
第１のデコーダと第２のデコーダに復号途中の上位ビットを記憶するメモリを設け、
上位ビットデコーダが、最大パスメトリックを求めると、当該パスメトリックに相当する候補の上位ビットを読み込んでパスメトリックを計算させ、上位ビットを復号することを特徴とする請求項９又は１０記載の復号装置。
【請求項１２】
請求項９乃至１１記載の復号装置におけるデコーダは、受信信号の硬判定結果の判定領域との距離が最小となる信号点を代表ブランチの候補信号点として記憶するルックアップテーブルを備え、入力される受信信号に対して前記ルックアップテーブルを参照し、代表ブランチの候補信号点を特定し、特定された候補信号点と受信信号の信号点との２乗ユークリッド距離を計算する２乗ユークリッド距離計算手段と、
計算された２乗ユークリッド距離の符号を反転したものと第１のデインタリーバからの出力を加算し、合算してブランチメトリックを計算するブランチメトリック計算手段と、
ブランチメトリックを加算して得られる前方パスメトリック又は後方パスメトリックを算出するパスメトリック算出手段と、
前方パスメトリックを記憶する前方パスメトリック記憶手段と、
前記ブランチメトリック、前記前方パスメトリック及び前記後方パスメトリックから最大パスメトリックの差分を計算する最大パスメトリック計算手段とを有することを特徴とするデコーダ。
【請求項１３】
ルックアップテーブルは、インデックス部とアドレス部から成るアドレステーブルと、アドレス部とデータ部から成るデータテーブルとを備え、
前記インデックス部におけるインデックスには、受信信号の硬判定結果と下位ｎビットの情報ビットとパリティビットを用い、前記データ部に１つのインデックスに対応して複数のデータが格納される場合には前記データ部内に継続ビットを設定することを特徴とする請求項８乃至１１のいずれか記載の復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、トレリス又はターボトレリス符号化変調方式における復号方法及び復号装置に係り、特に、復号処理の計算量を削減できるトレリス又はターボトレリス符号化変調方式における復号方法及び復号装置に関する。
【背景技術】
【０００２】
放送及び通信の分野では、近年、限られた周波数で符号化利得を得ることができるトレリス符号化変調方式が用いられている。
トレリス符号化変調方式とは、複数のサンプルの再生値の最適な組み合わせを複数の候補から選択するしくみとして、隣接するサンプルのとりうる再生値を制約することで、伝送ビット数を少なくするものである。
【０００３】
そこで、従来のトレリス符号化変調方式における符号装置について図１１を参照しながら説明する。図１１は、従来のトレリス符号化変調方式における符号装置の概略回路図である。
従来のトレリス符号化変調方式における符号装置は、図１１に示すように、情報シンボル（ｘ1 〜ｘ7 ）の７ビットを非符号化ビット（６ビット）と、１ビットを畳み込み符号化器１０１により拡大したビット（２ビット）をトレリス符号化シンボル８ビットとし、これを信号配置分配器１０３によりＩ軸とＱ軸の配置に対応した４ビットの送信側の変調データに変換し、変調して送出する。
【０００４】
トレリス符号装置は、トレリス符号化シンボルの８ビットの内、下位２ビットの符号化ビットの方が畳み込み符号化により符号間距離を大きく確保できる。また、上位の６ビットについては、変調シンボルの配置により符号距離を確保してバランスをとるようにしている。
【０００５】
また、従来のトレリス符号化変調方式における復号装置について図１２を参照しながら説明する。図１２は、従来のトレリス符号化変調方式における復号装置の概略回路図である。
従来のトレリス符号化変調方式における復号装置は、図１２に示すように、非符号化ビット復号部１２０と、ビタビ復号部１３０とから成る。
非符号化ビット復号部１２０は、代表シンボル検出手段１２７と、遅延手段１２８と、非符号化ビット選択手段１２９で構成される。
ビタビ復号部１３０は、ブランチメトリックユニット１３１と、ビタビ復号回路１３３と、たたみ込み符号化回路１３５で構成される。
【０００６】
上記復号装置のブランチメトリックユニット１３１は、軟判定された復調データからビタビ復号のためのブランチメトリックを計算し、ビタビ復号回路１３３で情報ビット（ｘ1 ）を得る。情報ビット（ｘ1 ）は、たたみ込み符号化回路１３５でたたみ込み符号化され、符号化ビット（ｙ0,ｙ1 ）を出力する。
【０００７】
上位ビットから代表シンボル検出手段１２７が各代表シンボルを検出し、ビタビ復号に掛かる時間分遅延手段１２８で遅延させ、たたみ込み符号化回路１３５から出力されるたたみ込み符号の符号化ビットにより非符号化ビット選択手段１２９は、非符号化ビットを選択して出力する。
【０００８】
トレリス復号に関する先行技術として、平成８年（１９９６年）２月２日公開の特開平８−３２６３３号公報「トレリス復号器」がある（特許文献１参照）。
この先行技術（先行技術１）は、トレリス復号器において、領域判定手段が、所定のビット配置で設定されるシンボル群の内から復調データによって特定される所定のシンボルの組に対応する領域情報を出力し、かつこの領域情報の一部のビットは当該シンボルの組の配置パターンに一致させた配置パターン情報と対応付け、振幅制御手段が、復調データに振幅制御を施し、ブランチメトリック演算手段が、振幅制御復調データの一部と配置パターン情報を用いてビダビ復号におけるブランチメトリックを演算するものである。
【０００９】
また、誤り訂正復号にビタビ復号を用いた先行技術として、平成１３年（２００１年）１２月１４日公開の特開２００１−３４５７８５号公報がある（特許文献２参照）。
この先行技術（先行技術２）は、シリアル／パラレル変換した送信データの内、１ビットの信号を畳み込み符号器に入力し、その出力の２ビットと畳み込み符号器に入力しなかった他の信号との組み合わせにより、それぞれ実数部と虚数部に分け、それぞれ独立に送出する信号点を決め、受信装置側でも実数部と虚数部で独立に領域判定し、メトリック設定を行い、実数部と虚数部とを合わせてビタビ復号化を行い、その結果を折り畳み符号器に入力して、その出力と領域判定の情報から送信データを復号するものである。
【００１０】
【特許文献１】特開平８−３２６３３号公報
【特許文献２】特開２００１−３４５７８５号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかしながら、上記従来のトレリス復号器では、ブランチメトリック計算処理において、並列遷移の全てのブランチを総当たりで計算するため、多値数の高い変調方式では計算量が飛躍的に増大するという問題点があった。
【００１２】
本発明は上記実情に鑑みて為されたもので、トレリス又はターボトレリス符号化変調方式において計算量を大幅に削減できる復号方法及び復号装置を提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記従来例の問題点を解決するための本発明は、トレリス符号化変調方式における復号方法であって、情報ビットの内、下位ｎビットを畳み込み符号化し、上位ビットは符号化せず、マッピングされて伝送される信号について、復号装置が、下位ｎビットの情報ビットが共通で、上位ビットが異なる並列遷移が存在するものとして、当該並列遷移の内、受信信号との距離が最も小さい信号点に対応する遷移を並列遷移の代表遷移として置き換えるに際して、予め受信信号の受信領域から遠い信号点に対するブランチを代表ブランチから除外したテーブルを形成しておき、当該テーブルを参照して代表ブランチの候補信号点を特定し、並列遷移の代表遷移への置き換えによって下位ｎビットのみに関するトレリス線図に置き換えて、下位ｎビットの情報ビットとパリティビットを合わせた下位ｎ＋１ビットを、ビタビアルゴリズムを用いて復号することを特徴とする。
【００１４】
本発明は、ターボトレリス符号化変調方式における復号方法であって、情報ビットの内、下位ｎビットをターボ符号化し、上位ビットは符号化せず、マッピングされて伝送される信号について、復号装置が、下位ｎビットの情報ビットが共通で、上位ビットが異なる並列遷移が存在するものとして、当該並列遷移の内、受信信号との距離が最も小さい信号点に対応する遷移を並列遷移の代表遷移として置き換えることで、下位ｎビットのみに関するトレリス線図に置き換えて、下位ｎビットの情報ビットとパリティビットを合わせた下位ｎ＋１ビットを、Max-log MAP アルゴリズムを用いた繰り返し復号により復号することを特徴とする。
【００１５】
本発明は、上記ターボトレリス符号化変調方式における復号方法において、並列遷移へ置き換えは、予め受信信号の受信領域から遠い信号点に対するブランチを代表ブランチから除外したテーブルを形成しておき、当該テーブルを参照して代表ブランチの候補信号点を特定することで為されることを特徴とする。
【発明の効果】
【００１６】
本発明によれば、トレリス符号化変調方式における復号方法であって、情報ビットの内、下位ｎビットを畳み込み符号化し、上位ビットは符号化せず、マッピングされて伝送される信号について、復号装置が、下位ｎビットの情報ビットが共通で、上位ビットが異なる並列遷移が存在するものとして、当該並列遷移の内、受信信号との距離が最も小さい信号点に対応する遷移を並列遷移の代表遷移として置き換えるに際して、予め受信信号の受信領域から遠い信号点に対するブランチを代表ブランチから除外したテーブルを形成しておき、当該テーブルを参照して代表ブランチの候補信号点を特定し、並列遷移の代表遷移への置き換えによって下位ｎビットのみに関するトレリス線図に置き換えて、下位ｎビットの情報ビットとパリティビットを合わせた下位ｎ＋１ビットを、ビタビアルゴリズムを用いて復号するものであり、トレリス符号化変調方式において計算処理量を削減できる効果がある。
【００１７】
本発明によれば、ターボトレリス符号化変調方式における復号方法であって、情報ビットの内、下位ｎビットをターボ符号化し、上位ビットは符号化せず、マッピングされて伝送される信号について、復号装置が、下位ｎビットの情報ビットが共通で、上位ビットが異なる並列遷移が存在するものとして、当該並列遷移の内、受信信号との距離が最も小さい信号点に対応する遷移を並列遷移の代表遷移として置き換えることで、下位ｎビットのみに関するトレリス線図に置き換えて、下位ｎビットの情報ビットとパリティビットを合わせた下位ｎ＋１ビットを、Max-log MAP アルゴリズムを用いた繰り返し復号により復号する復号方法としているので、ターボトレリス符号化変調方式においても計算処理量を削減できる効果がある。
【００１８】
本発明によれば、並列遷移へ置き換えが、予め受信信号の受信領域から遠い信号点に対するブランチを代表ブランチから除外したテーブルを形成しておき、当該テーブルを参照して代表ブランチの候補信号点を特定することで為される上記ターボトレリス符号化変調方式における復号方法としているので、テーブルを参照することで計算量を減らし、処理速度を向上させることができる効果がある。
【発明を実施するための最良の形態】
【００１９】
本発明の実施の形態について図面を参照しながら説明する。
本発明の一実施の形態に係るトレリス符号化変調方式における復号方法は、情報ビットの内、下位ｎビットを符号化し、上位ビットは符号化せず、マッピングされて伝送される信号について、下位ｎビットの情報ビットが共通で、上位ビットが異なる並列遷移が存在するものとして、当該並列遷移の内、受信信号との距離が最も小さい信号点に対応する遷移を並列遷移の代表遷移として置き換えるに際して、予め受信信号の受信領域から遠い信号点に対するブランチを代表ブランチから除外したテーブルを形成しておき、当該テーブルを参照して代表ブランチの候補信号点を特定し、並列遷移の代表遷移への置き換えによって下位ｎビットのみに関するトレリス線図に置き換えることができ、ｎビットの情報ビットとパリティビットを合わせたｎ＋１ビットを復号するものであり、トレリス符号化変調方式において計算処理量を削減できる効果がある。
【００２０】
本発明の一実施の形態に係るターボトレリス符号化変調方式における復号方法は、情報ビットの内、下位ｎビットをターボ符号化し、上位ビットは符号化せず、マッピングされて伝送される信号について、復号装置が、下位ｎビットの情報ビットが共通で、上位ビットが異なる並列遷移が存在するものとして、当該並列遷移の内、受信信号との距離が最も小さい信号点に対応する遷移を並列遷移の代表遷移として置き換えることで、下位ｎビットのみに関するトレリス線図に置き換えて、下位ｎビットの情報ビットとパリティビットを合わせた下位ｎ＋１ビットを、 Max-log MAP アルゴリズムを用いた繰り返し復号により復号するものであり、ターボトレリス符号化変調方式において計算処理量を削減できる効果がある。
【００２１】
［簡易復号アルゴリズムの検討］
まず、本発明の一実施の形態に係るトレリス符号化変調方式における基本的な考えを説明する。
本発明の実施の形態に係る基本的な考え方は、トレリス符号化変調方式において、下位ｎビットのみを符号化して、上位ビットは符号化せずにマッピングして伝送していることを利用して、多値数が増えた場合にも、計算量が少ない復号アルゴリズムを採用している。
つまり、下位ｎビットのみを符号化しているということは、符号トレリスにおいて、下位ｎビットの情報ビットが共通で、上位ビットが異なる並列遷移が存在することを意味している。
【００２２】
この並列遷移の内、受信信号との距離が最も小さい信号点に対応する遷移を並列遷移の代表遷移として並列遷移を一つの遷移に置き換えるものである。そうすると、下位ｎビットのみの関するトレリス線図に置き換えられ、これを用いて、下位ｎビットの情報ビットとパリティビットを合わせた下位ｎ＋１ビットをビタビにより復号を行う。上位ビットは、下位ｎ＋１ビットが決まった後に最も受信信号に近い信号点を求め、その上位ビットを復号結果とする。上記の復号アルゴリズムにおいて、並列遷移の中で受信信号に最も近いブランチに限定して行う復号を本発明の実施の形態に係る簡易復号アルゴリズム又は単に簡易復号アルゴリズムと呼ぶことにする。
【００２３】
［簡易復号アルゴリズムの高速化］
簡易復号アルゴリズムのブランチメトリック計算の中には、並列遷移の中で代表ブランチを決定するための比較演算がある。この比較演算は入力ビット数ｍに対して指数関数的に増えるため、入力ビット数が多い場合には問題となる。
【００２４】
この代表ブランチを決定する処理と同じ処理が、下位ｎ＋１ビットが決定されたときに、次に上位ビットを求める処理でも用いられる。これは、最大パスが求められた場合に、当該最大パスに関する復号装置のメモリの内部状態の情報又は下位ビットの情報に基づいて、改めて上位ビットを求める処理を行うためである。
尚、最大パスを求める過程で上位ビットをＲＡＭ等のメモリに記憶するようにすれば、改めて上位ビットを求める処理は不要となる。
【００２５】
上記比較演算数を削減できれば、特に２度行う処理の場合に、演算量削減の効果が得られる。以下、この比較演算数を削減する方法を提案する。
【００２６】
［比較演算数削減の基本アイディア］
提案する方法は、受信信号の硬判定結果を補助情報として利用するもので、簡単のため、１６−ＱＡＭ（Quadrature Amplitude Modulation：直交振幅変調）を例に図１及び図２を参照しながら説明する。図１は、１６−ＱＡＭの硬判定領域を示す概略図であり、図２は、候補信号点の決定例を示す概略図である。
【００２７】
尚、ＱＡＭは、デジタルデータをアナログ信号に変換する変調方式の一つで、変換された後の波の振幅と位相の両方を使って情報を表現するため、限られた帯域幅で効率よくデータを伝送することができる。
【００２８】
この場合、受信信号の硬判定は、受信信号を図１のような判定領域で判定することで得られるものである。受信信号の硬判定結果に対応する判定領域を受信領域と呼ぶことにする。
【００２９】
本発明の実施の形態では、受信領域から遠い信号点に対応するブランチを、代表ブランチ選択の候補から除くことで、計算量を減らすことを提案している。代表ブランチ選択の候補として残されたブランチに対応する信号点を候補信号点と呼ぶことにする。
この候補信号点は、以下の方法で予め決定してテーブルに格納しておき、受信信号の硬判定結果と下位ｎ＋１ビットからテーブルルックアップで得られるようにしておく。
次に、候補信号点をどのように決定するかについて説明する。
【００３０】
［受信信号の硬判定結果を用いた候補信号点の決定］
以下では、ｎ＝２の例で説明する。
まず、記号の定義を行う。ｋ時点の受信信号の硬判定結果、無符号化上位ビット、符号化された情報２ビット、パリティビット、送信シンボルの下位３ビットを以下の［数１］に表す。
【００３１】
【数１】
2006173724.tif 000003
【００３２】
並列遷移の代表ブランチを決定する処理は、送信シンボルの下位３ビットが決まったとき、受信信号に最も近い信号点を決定する処理となる。このとき、代表ブランチ選択の比較対象となる全信号点の集合、硬判定結果を考慮して得られた候補信号点の集合を以下の［数２］に表す。
【００３３】
【数２】
2006173724.tif 000004
【００３４】
例を用いて、図２及び以下の［数３］を参照しながら候補信号点の決定方法を説明する。
【数３】
2006173724.tif 000005
【００３５】
しかし、これだけでは、（１０）8 を除外することはできない。判定領域の中に（００）8 よりも（１０）8 に近い領域があった場合には（１０）8 を除外できないからである。
そこで、信号点（００）8 と信号点（１０）8 を結ぶ線分に対する垂直２等分線を考え、もし、垂直２等分線が判定領域外を通れば、判定領域内に信号点（００）8 よりも信号点（１０）8 に近い領域が存在しないことになる。従って、候補信号点は（００）8 に決まるものである。
【００３６】
もし、垂直２等分線が判定領域内を通れば、判定領域内に信号点（００）8 よりも信号点（１０）8 に近い領域が存在することになる。この場合、両方とも候補信号点となる。
【００３７】
図２の例では、垂直２等分線は、判定領域外を通るので、信号点（１０）8 を除外でき、候補信号点の集合は、以下の［数４］の通りとなる。
【００３８】
【数４】
2006173724.tif 000006
【００３９】
［トレリス符号化変調システムにおける符号装置］
本発明の一実施の形態にトレリス符号化変調システムにおける符号装置について図３を参照しながら説明する。図３は、本発明の一実施の形態に係るトレリス符号化変調システムにおける符号装置の概略構成図である。
本発明の一実施の形態に係る符号装置（第１の符号装置）は、図３に示すように、エンコーダ６１と、マッピング回路６２とを基本的に備えている。
【００４０】
第１の符号装置におけるエンコーダ６１は、下位ビットｄ1k，ｄ2kを畳み込み符号化して、パリティ１ビットｐk を付加してマッピング回路６２に出力する。
マッピング回路６２は、上位ビットｄ3k…ｄmkは符号化せず入力し、エンコーダ６１から畳み込み符号化した下位ビット及びパリティビットを入力して、ＱＡＭにより変調を行う。変調方式は、１６−ＱＡＭ、２５６−ＱＡＭ等が用いられる。
【００４１】
［トレリス符号化変調システムにおける復号装置］
また、本発明の一実施の形態に係るトレリス変調システムにおける復号装置について図４を参照しながら説明する。図４は、本発明の一実施の形態に係るトレリス変調システムにおける復号装置の概略回路図である。
本発明の一実施の形態に係る復号装置（第１の復号装置）は、図４に示すように、デコーダ１と、硬判定ブロック２と、上位ビットデコーダ３とを基本的に有している。
【００４２】
［第１の復号装置のデコーダ］
第１の復号装置におけるデコーダ１は、ビタビアルゴリズムをベースとした簡易復号アルゴリズムにより復号を行うものであり、ルックアップテーブルを参照して代表ブランチを特定し、パスメトリックを算出する。
デコーダ１は、２乗ユークリッド距離計算手段１１と、ブランチメトリック計算手段１２と、前方パスメトリック計算手段１３とを備えている。
尚、上記各手段は、例えば、ＤＳＰ（Digital Signal Processor）等で実現されるものである。
【００４３】
２乗ユークリッド距離計算手段１１は、代表ブランチを求めるために、受信信号の硬判定の信号点に対して代表ブランチ選択の比較対象となる候補信号点を特定するルックアップテーブルを記憶するＲＯＭ（Read Only Memory）を備え、当該ルックアップテーブルを参照して、受信信号の信号点に対応する候補信号点を特定し、受信信号の信号点と候補信号点との２乗ユークリッド距離を計算し、代表ブランチの２乗ユークリッド距離を出力する回路である。
【００４４】
尚、ルックアップテーブルを参照した結果、候補信号点が複数ある場合には、計算されたユークリッド距離が短い方の候補信号点を代表ブランチとして決定されるものである。
【００４５】
ブランチメトリック計算手段（γ）１２は、２乗ユークリッド距離計算手段１１から出力された代表ブランチの２乗ユークリッド距離の符号を反転したブランチメトリックを計算する回路である。
【００４６】
トレリスの連続する枝（ブランチ）をつないで作られるデータ系列はパスと呼ばれ、パスに沿ってブランチメトリックを加算して得られる値をパスメトリックと呼ぶ。
【００４７】
前方パスメトリック計算手段（α）１３は、時刻０（ゼロ）からの時系列のパスメトリック（前方パスメトリック）について、ある特定時刻におけるパスメトリックを算出する回路である。
【００４８】
［硬判定ブロック］
硬判定ブロック２は、前方パスメトリック計算手段１３からの出力を硬判定することにより、情報ビットの下位２ビットとパリティビットを合わせた送信シンボルの下位３ビットが得られる。
【００４９】
［上位ビットデコーダ］
上位ビットデコーダ３は、硬判定ブロック２で得られた送信シンボルの下位３ビットと受信信号が入力され、下位３ビットが決まったという条件で最も受信信号に近い信号点を求めることで、上位ビットを復号する。
尚、硬判定ブロック２と上位ビットデコーダ３とは、例えば、ＤＳＰを用いて実現されるものである。
【００５０】
［メモリ有無の２つのタイプ］
ここで、第１の復号装置には、２乗ユークリッド距離計算手段１１において、代表ブランチに対する上位ビットを記憶するメモリ（ＲＡＭ：Random Access Memory）を備えるタイプと、そのようなメモリを備えないタイプの２つのタイプがある。
【００５１】
メモリを備えるタイプであれば、上位ビットデコーダ３は、最大パスメトリックが求められたときに、当該最大パスメトリックに対応する候補の上位ビットを２乗ユークリッド距離計算手段１１のＲＡＭから読み込みパスメトリックを算出するものである。
【００５２】
また、メモリを備えないタイプであれば、上位ビットデコーダ３は、最大パスメトリックを求める過程で時系列に記憶した代表ブランチのパスの状態又は下位３ビットに基づいて再度デコードすることで上位ビットを復号するものである。
【００５３】
［ルックアップテーブル］
次に、第１の復号装置におけるデコーダ１の２乗ユークリッド距離計算手段１１に設けられたＲＯＭ内のルックアップテーブルについて図５を参照しながら説明する。図５は、ルックアップテーブルの概略図である。
ルックアップテーブルは、図５に示すように、アドレステーブル（Address Table）とデータテーブル（Data Table）とから構成されている。
【００５４】
アドレステーブルは、インデックス部（Index）とアドレス部（Address）とを有し、データテーブルは、アドレス部（Address）とデータ部（Data）とを有している。
インデックス部は、下位３ビット（情報２ビットとパリティ１ビット）と硬判定結果が設定され、それらをインデックスとしてデータ（候補信号点の集合）にアクセスするアドレスが特定され、当該アドレスにデータが対応付けられている。
【００５５】
データ部におけるデータの末尾には継続ビット０，１が付加されるようになっている。継続ビットが１であれば、次のデータも同じインデックスに対応した別の候補信号点であることを示しており、継続ビットが０であれば、そのデータをもって候補信号点の集合が終わりであることを示している。
【００５６】
尚、データ部において、候補信号点の集合で候補信号点の数が１，２，３，…と様々であるため、ＲＯＭを隙間なく使うために、インデックスから直接にデータを参照するのではなく、インデックスから必要なデータの先頭アドレスを参照するためのルックアップテーブルとしている。
【００５７】
ルックアップテーブルは、図１及び図２を用いて説明した、受信信号の信号点に対して予め求めた候補信号点の集合がデータ部に格納しておくものであり、並列遷移の代表遷移を決定する処理の場合に参照されるものとなっている。
【００５８】
［第１の復号装置の動作］
次に、第１の復号装置の動作を説明する。
デコーダ１の２乗ユークリッド距離計算１１は、受信信号Ｒk の信号点に対してＲＯＭ内のルックアップテーブルを参照して代表ブランチを特定し、代表ブランチの２乗ユークリッド距離を計算し、ブランチメトリック計算手段１２に出力する。
【００５９】
ブランチメトリック計算手段１２は、代表ブランチの２乗ユークリッド距離の符号を反転したブランチメトリックを計算し、前方パスメトリック計算手段１３に出力する。
前方パスメトリック計算手段１３は、時系列にブランチメトリックを加算し、得られたパスメトリックを硬判定ブロック２に出力する。
【００６０】
硬判定ブロック２は、パスメトリックを硬判定することにより、情報ビットの下位２ビットとパリティビットを合わせた送信シンボルの下位３ビットを取得し、上位ビットデコーダ３に出力する。
上位ビットデコーダ３は、送信シンボルの下位３ビットと受信信号とから、下位３ビットが決まったという条件で最も受信信号に近い信号点を求める方法で、上位ビットを復号する。
【００６１】
［ターボＴＣＭシステム］
本発明の別の一実施の形態に係るターボトレリス符号化変調システムは、シャノン限界に近い誤り率特性をもつターボ符号を多値変調に拡張し、周波数利用効率を高めたターボトレリス符号化変調（ターボＴＣＭ）システムに関するものである。
【００６２】
ターボＴＣＭシステムにおいて、多値数が高い場合、符号トレリスのブランチ数が増加するため、復号アルゴリズム（Max-log MAP）の処理量の増加を引き起こす。そこで、上述したとおり、Max-log MAPをベースにした簡易復号アルゴリズムを採用することで、処理量を削減し、処理の高速化を実現するものである。
【００６３】
従来の Max-log MAP アルゴリズムは、並列遷移ブランチ全てを対象として繰り返し復号を行うものであるのに対して、本発明の別の一実施の形態に係る簡易復号アルゴリズムは、並列遷移の中で受信信号に最も近いブランチに限定して繰り返し復号を行う。
【００６４】
すなわち、このブランチに限定して外部値の計算（事前値）を行っているため、処理速度は向上するが、復号特性が従来の Max-log MAP アルゴリズムに比べて劣化する可能性がある。計算機シミュレーションにより、両者の特性を比較した結果、特性劣化はほとんどないことが分かった。
尚、Max-log MAP アルゴリズムについては、1999年トリケップス発行、荻原春生編集「ターボ符号の基礎」第４章 2.4 Log-MAPアルゴリズム・Max-log-MAPアルゴリズムに詳しく記載されている。
【００６５】
［第２の符号装置］
次に、本発明の別の一実施の形態に係るターボトレリス符号化変調システムにおける符号装置について図６を参照しながら説明する。図６は、本発明の別の一実施の形態に係る符号装置の概略回路図である。
本発明の別の一実施の形態に係る符号装置（第２の符号装置）は、図６に示すように、ターボトレリス符号装置であり、エンコーダ７１ａ，７１ｂと、インタリーバ７３と、デインタリーバ７４と、マッピング回路７２とを基本的に有している。
【００６６】
以下、ｎ＝２の例で説明する。
図６では、下位２ビットのみをターボ符号で符号化し、上位ビットは符号化せずにマッピングして伝送する構成となっている。尚、出力シンボルの信号点へのマッピングは、集合分割により割り当てられている。
【００６７】
エンコーダ７１ａ，７１ｂは、要素符号器で、組織型再帰的畳み込み符号器が用いられる。
エンコーダ７１ａは、下位２ビットを入力し、１ビットのパリティビットを生成する。
インタリーバ７３は、入力された情報の順序を入れ替えてエンコーダ７１ｂに出力する。
エンコーダ７１ｂは、インタリーバ７３からの出力から１ビットのパリティビットを生成し、デインタリーバ７４に出力する。
デインタリーバ７４は、エンコーダ７１ｂが生成したパリティビットを元の情報の位置に戻す処理を行う。
【００６８】
エンコーダ７１ａで生成されたパリティビットと、デインタリーバ７４から出力されるパリティビットは、交互に間引かれる（パンクチャされる）。
そして、上位ビット、下位２ビット、パリティビットをマッピング回路７２で、例えば、２５６−ＱＡＭにマッピングし、通信路に送信する。
【００６９】
［第２の復号装置］
次に、本発明の別の一実施の形態に係るターボトレリス変調システムにおける復号装置について図７を参照しながら説明する。図７は、本発明の別の一実施の形態に係る復号装置の概略回路図である。
本発明の別の一実施の形態に係る復号装置（第２の復号装置）は、図７に示すように、ターボトレリス復号装置であり、デコーダ１ａ，１ｂと、硬判定ブロック２ａ，２ｂと、上位ビットデコーダ３′と、インタリーバ４と、デインタリーバ５ａ，５ｂと、加算器６ａ，６ｂとを基本的に有している。
【００７０】
デコーダ１ａは、Max-log MAPをベースとした簡易復号アルゴリズムにより復号を行うものであり、デインタリーバ５ａからの出力と受信信号を入力し、ルックアップテーブルを参照して代表ブランチを特定し、最大パスメトリックを算出する。
加算器６ａは、デインタリーバ５ａからの出力の符号を反転したものとデコーダ１ａからの出力を加算してインタリーバ４に出力する。
インタリーバ４は、加算器６ａからの出力について情報の入れ替えを行い、デコーダ１ｂと加算器６ｂに出力すると共に、受信信号を入力し、情報の入れ替えを行い、デコーダ１ｂに出力する。
【００７１】
デコーダ１ｂは、Max-log MAPをベースとした簡易復号アルゴリズムにより復号を行うものであり、加算器６ａからの出力であって、インタリーバ４で入れ替えられた情報について、ルックアップテーブルを参照して代表ブランチを特定し、最大パスメトリックを算出し、加算器６ｂに出力すると共に、インタリーバ４で入れ替えられた受信信号について、ルックアップテーブルを参照して代表ブランチを特定し、最大パスメトリックを算出し、硬判定ブロック２ｂに出力する。
【００７２】
加算器６ｂは、インタリーバ４からの出力の符号を反転したものとデコーダ１ｂからの出力を加算してデインタリーバ５ａに出力する。
デインタリーバ５ａは、加算器６ｂで加算された情報を元の順序に戻し、デコーダ１ａと加算器６ａに出力する。
【００７３】
また、硬判定ブロック２ａは、デコーダ１ａで復号された受信信号について硬判定を行い、パリティビットｐ1kを生成して出力する。
硬判定ブロック２ｂは、インタリーバ４で入れ替えられ、デコーダ１ｂで復号された受信信号について硬判定を行い、情報２ビットとパリティビットの下位３ビットを生成して出力する。
【００７４】
デインタリーバ５ｂは、硬判定ブロック２ｂからの下位３ビットを元の順序に並び替え、情報２ビットとパリティビットを出力する。
上位ビットデコーダ３′は、デインタリーバ５ｂから情報２ビットを入力し、パリティビットについては、送信時のパンクチャに合わせて硬判定ブロック２ａ又はデインタリーバ５ｂで得られたいずれかを選択する。
送信時にエンコーダ１のパリティが送信された時点に対応する復号の際は、硬判定ブロック２ａから出力されるパリティビットを選択し、送信時にエンコーダ２のパリティが送信された時点に対応する復号の際は、デインタリーバ５ｂから出力されるパリティビットを選択する。
そして、上位ビットデコーダ３′は、送信シンボルの下位３ビット（情報２ビットとパリティビット）と受信信号とから、下位３ビットが決まったという条件で最も受信信号に近い信号点を求める方法で、上位ビットを復号する。
【００７５】
図７のターボトレリス復号装置は、情報ビットの下位２ビットとパリティビットを合わせた送信シンボルの下位３ビットに対するターボＴＣＭ復号器を表している。この復号器において、外部値は符号化した情報ビットに対して求められ、他の復号器の事前値として渡される。
【００７６】
この復号器において、事後値Λは、情報ビットとパリティビットを合わせたものに対して求められる。これを硬判定することにより情報ビットとパリティビットが得られる。
【００７７】
デコーダ１ｂの復号結果をデインタリーブして系列順を戻し、パリティビットｐ1kとｐ2kをパンクチャし、情報ビットと合わせることで、通信路に送られたシンボルの下位３ビットが得られる。これと受信信号が上位ビットデコーダ３′に入力されて、上位ビットが復号される。
【００７８】
［第２の復号装置のデコーダ］
次に、第２の復号装置の第１及び第２のデコーダの構成について図８を参照しながら説明する。図８は、第２の復号装置の第１及び第２のデコーダの構成ブロック図である。
第２の復号装置のデコーダは、図８に示すように、２乗ユークリッド距離計算手段１１と、ブランチメトリック計算手段（γ）１２′と、パスメトリック計算手段（α）（β）１３′と、前方パスメトリック記憶手段（α  ＲＡＭ）１４と、最大パスメトリック計算手段（Λ）１５とを基本的に有している。
尚、上記各手段は、例えば、ＤＳＰ（Digital Signal Processor）等で実現されるものである。
【００７９】
２乗ユークリッド距離計算手段１１は、代表ブランチを求めるために、受信信号の硬判定の信号点に対して代表ブランチ選択の比較対象となる候補信号点を特定するルックアップテーブルを記憶するＲＯＭ（Read Only Memory）を備え、当該ルックアップテーブルを参照して、受信信号の信号点に対応する候補信号点を特定し、受信信号の信号点と候補信号点との２乗ユークリッド距離を計算し、代表ブランチの２乗ユークリッド距離を出力する回路である。
【００８０】
尚、ルックアップテーブルを参照した結果、候補信号点が複数ある場合には、計算された２乗ユークリッド距離が短い方の候補信号点を代表ブランチとして決定されるものである。
また、ルックアップテーブルについては、図５を用いて既に説明している。
【００８１】
ブランチメトリック計算手段（γ）１２′は、事前値と２乗ユークリッド距離計算手段１１から出力された代表ブランチの２乗ユークリッド距離の符号を反転したものとを加算して合算し、ブランチメトリックを計算する回路である。
【００８２】
パスメトリック計算手段（α）（β）１３′は、時刻０（ゼロ）からの時系列のパスメトリック（前方パスメトリック：α）と時刻を遡って求めたパスメトリック（後方パスメトリック：β）について、ある特定時刻におけるパスメトリックを算出する回路である。
【００８３】
前方パスメトリック記憶手段（α  ＲＡＭ）１４は、パスメトリックの計算が最初前方パスメトリックから行われるので、その前方パスメトリック（α）を記憶するメモリである。
【００８４】
尚、前方パスメトリックを計算する場合は、受信信号を前方向から２乗ユークリッド距離計算手段１１に入力し、後方パスメトリックを計算する場合は、受信信号を後方向から２乗ユークリッド距離計算手段１１に入力する。このように、２度の受信信号の前方向と後方向からの入力によって、前方パスメトリックと後方パスメトリックを算出するようになっている。
【００８５】
最大パスメトリック計算手段（Λ）１５は、ブランチメトリック計算手段１２′からブランチメトリック（γ）を、パスメトリック計算手段１３′から後方パスメトリック（β）を、前方パスメトリック記憶手段１４から前方パスメトリック（α）を入力して、最大パスメトリックを出力する。
【００８６】
［メモリ有無の２つのタイプ］
また、第２の復号装置においても、２乗ユークリッド距離計算手段１１において、代表ブランチに対する上位ビットを記憶するメモリ（ＲＡＭ：Random Access Memory）を備えるタイプと、そのようなメモリを備えないタイプの２つのタイプがある。
【００８７】
メモリを備えるタイプであれば、上位ビットデコーダ３′は、最大パスメトリックが求められたときに、当該最大パスメトリックに対応する候補の上位ビットを採用したデコーダの２乗ユークリッド距離計算手段１１のＲＡＭから読み込みパスメトリックを算出するものである。
【００８８】
また、メモリを備えないタイプであれば、上位ビットデコーダ３は、最大パスメトリックを求める過程で時系列に記憶した代表ブランチのパスの状態又は下位３ビットに基づいて再度デコードすることで上位ビットを復号するものである。
【００８９】
図７に示したハードウェア構成を用いる場合で、２５６−ＱＡＭの場合のルックアップテーブルを作成してみると、全インデックスに対する候補信号点の数の割合が図９のようになる。図９は、ルックアップテーブルにおける候補信号数に対するインデックスの数と割合を示す図である。
【００９０】
尚、候補信号点数が５以上のインデックスは存在せず、図９を参照すると、大部分のインデックスに対して復号候補信号点は１つに決まることが分かる。
また、インデックスに対する平均候補数は１．５であった。総当たり比較での並列遷移の代表遷移を決定する場合、比較対象数は、２８−３＝３２であるので、これに比べると、比較回数を大幅に減らすことができる。
【００９１】
また、第２の復号装置を用いた場合の復号法の計算量を図１０に、従来の復号法の計算量を図１３に示す。図１０は、本発明の実施の形態に係る復号法の計算量を示す図であり、図１３は、従来の復号法の計算量を示す図である。尚、この計算量は、トレリスの１遷移区間当たりの計算量となっている。また、Ｎｓは要素符号器の状態数を表している。直感的理解を助けるため、ｍ＝７，Ｎｓ＝８としたときの計算量を併せて示している。
【００９２】
また、図１０におけるルックアップテーブルのインデックスに対する平均候補数を１．５としている。テーブルルックアップの欄で、１＋１．５となっているのは、１がアドレステーブル参照回数であり、１．５がデータテーブル参照回数であり、よって両者を合計している。
【００９３】
図１０と図１３とを比較すると、実施の形態に係る簡易復号アルゴリズムによる計算量は、従来の計算量の１／１０程度となった。
特に、ブランチメトリックの計算量が大幅に削減されている。これは、総当たりで並列遷移のブランチメトリックを計算することを避けた効果である。
また、上位ビット決定処理を比較すると、その計算量も大幅に削減されている。
【００９４】
本発明の実施の形態によれば、符号トレリスの中で無符号化上位ビットによる並列遷移ブランチの中から受信信号に最も近い信号点に対応するブランチを代表ブランチとして、そのブランチに限定して繰り返す復号を行うことで、特性の劣化なしに、計算処理量を従来のMax-log MAPより減らすことができる効果がある。
【００９５】
更に、代表ブランチを求める際に、受信信号の硬判定結果を利用して、受信信号から遠くの信号点に対応するブランチを代表ブランチの候補から除外し、不要な比較を避けることで、処理量の削減を行った。これは、予めルックアップテーブルを用意することで実現できるものである。
【産業上の利用可能性】
【００９６】
本発明は、トレリス又はターボトレリス符号化変調方式において計算量を大幅に削減できる復号方法及び復号装置に好適である。
【図面の簡単な説明】
【００９７】
【図１】１６−ＱＡＭの硬判定領域を示す概略図である。
【図２】候補信号点の決定例を示す概略図である。
【図３】本発明の一実施の形態に係るトレリス符号化変調システムにおける符号装置の概略構成図である。
【図４】本発明の一実施の形態に係るトレリス変調システムにおける復号装置の概略回路図である。
【図５】ルックアップテーブルの概略図である。
【図６】本発明の別の一実施の形態に係るターボトレリス符号化変調システムにおける符号装置の概略回路図である。
【図７】本発明の別の一実施の形態に係るターボトレリス符号化変調システムにおける復号装置の概略回路図である。
【図８】第２の復号装置の第１及び第２のデコーダの構成ブロック図である。
【図９】ルックアップテーブルにおける候補信号数に対するインデックスの数と割合を示す図である。
【図１０】本発明の実施の形態に係る復号法の計算量を示す図でである。
【図１１】従来のトレリス符号化変調方式における符号装置の概略回路図である。
【図１２】従来のトレリス符号化変調方式における復号装置の概略回路図である。
【図１３】従来の復号法の計算量を示す図である。
【符号の説明】
【００９８】
１，１ａ，１ｂ…デコーダ、  ２，２ａ，２ｂ…硬判定ブロック、  ３，３′…上位ビットデコーダ、  ４…インタリーバ、  ５ａ．５ｂ…デインタリーバ、  ６ａ．６ｂ…加算器、  １１…２乗ユークリッド距離計算手段、  １２，１２′…ブランチメトリック計算手段、  １３…前方パスメトリック計算手段、  １３′…パスメトリック計算手段、  １４…前方パスメトリック記憶手段、  １５…最大パスメトリック計算手段、  ６１，７１ａ，７１ｂ…エンコーダ、  ６２，７２…マッピング回路、  ７３…インタリーバ、  ７４…デインタリーバ
【図１】
2006173724.tif 000007
【図２】
2006173724.tif 000008
【図３】
2006173724.tif 000009
【図４】
2006173724.tif 000010
【図５】
2006173724.tif 000011
【図６】
2006173724.tif 000012
【図７】
2006173724.tif 000013
【図８】
2006173724.tif 000014
【図９】
2006173724.tif 000015
【図１０】
2006173724.tif 000016
【図１１】
2006173724.tif 000017
【図１２】
2006173724.tif 000018
【図１３】
2006173724.tif 000019