JP2017005285A - 復号装置 - Google Patents

Abstract

【課題】復号計算における計算量を削減する事のできる復号装置を得る。【解決手段】伝送路上で発生する伝送誤りを訂正するための誤り訂正符号の復号を行う復号装置において、検査行列に代えて生成行列を用いて復号計算を行う消失訂正復号部２２を備える。消失訂正復号部２２は、受信成功したパケットに対応する生成行列の列または行を並べ替えて、受信成功したパケットに対応する部分行列を構成し、消失したパケットに対応する行列に関しては削除した上で復号計算を行う。【選択図】図１

Description

本発明は、伝送路上で発生する伝送誤りを訂正するための誤り訂正符号の符号化を行う送信機に含まれる符号化装置から符号化されたパケットが伝送された前提で、受信機側で受信したパケットを復号する復号装置に関する。

一般的な消失訂正の符号化／復号は、例えば消失訂正符号を用いて送信機側でパケット単位で符号化を行い、受信機側は、通信路により部分的に消失したパケット列を受信し、受信成功したパケットに基づいてガウス消去法等により消失したパケットを復号する。なお、消失したパケットとは受信に失敗したパケットの事であり、受信に失敗したパケットはそのパケットを構成するすべてのビットに関する情報が得られないため、消失したと表現する。このような従来の復号法としては例えば非特許文献１に示されているようなものがあった。なお、明細書中、情報ビットの固まりをパケットと表現しているが、ブロックという表現でも構わず、同じ効果を奏する。ここでは便宜上パケットという表現に限定して説明する。

室津、和田山、山北、"ＢＰとガウス消去法を組み合わせたＬＤＰＣ符号の消失誤り訂正法"、ＳＩＴＡ２００４、２７（１），２７１−２７４，２００４−１２−１４

しかしながら、復号法は一般に検査行列の“１”の数に相当する計算量が必要となり行数×列数の大きさに依存したメモリ量と計算量が必要となる。
従来手順では、受信成功パケットをすべて保存し、検査行列からガウス消去法の結果に従って計算する必要がある。この場合、検査行列と受信成功パケットの積が全て０になる事を確認する必要があり、受信時のパケット誤り率に係わらず、少なくともほぼ“１”の数に比例する計算量以上の計算が必要になり、計算量が多いという問題があった。

この発明は上記のような課題を解決するためになされたもので、復号計算における計算量を削減する事のできる復号装置を得る事を目的とする。

この発明に係る復号装置は、伝送路上で発生する伝送誤りを訂正するための誤り訂正符号の復号を行う復号装置において、検査行列に代えて生成行列を用いて復号計算を行う消失訂正復号部を備えたものである。

この発明の復号装置は、誤り訂正符号の復号を行う際、生成行列を用いて復号計算を行うようにしたので、復号計算の計算量を削減する事ができる。その結果、処理能力の低いＣＰＵでも動作できるため、より低価格の通信システムに消失訂正符号化復号機能を搭載できる効果がある。または、処理能力のＣＰＵの場合は、より高速な処理を実現できる効果がある。

この発明の実施の形態１による復号装置を示す構成図である。 この発明の実施の形態３による復号装置の情報パケット数に対応したαの値を示す説明図である。

実施の形態１．
図１は、この発明の実施の形態１による復号装置を適用した通信システムを示す構成図である。
図示の通信システムは、送信機１０と受信機２０とを備える。送信機１０は符号化装置であり、パケット生成部１１、消失訂正符号化部１２、送信部１３を備える。受信機２０は復号装置であり、受信部２１、消失訂正復号部２２、情報ビット再生部２３を備える。

送信機１０において、パケット生成部１１は、検査行列を用いて、情報ビットからパケットを生成する処理部である。消失訂正符号化部１２は、パケットを消失誤り訂正符号化する処理部である。送信部１３は、符号化されたパケットを通信路３０を経由して受信機２０へ送信するための処理部である。

受信機２０において、受信部２１は、通信路３０を経由して送信機１０から送信されたパケットを受信する。消失訂正復号部２２は、これらパケットに対して、誤り検出及び消失訂正を行う処理部である。情報ビット再生部２３は、復号化したパケットを結合して、情報ビットを生成する処理部である。

実施の形態１の動作説明に先立ち、先ず、消失訂正符号の符号化方法及び復号方法について説明する。説明を簡略化するため、以降各パケットは１ビットの情報で構成されているものとする。実際には以降で示す処理は各パケットに複数ビット含まれており、同じ処理が並列して実行される。
符号化パケットベクトルｖ＝（ｕ｜ｐ）としｕ＝（ｕ₁ ｕ₂…ｕ_k）をｋ個のパケットからなる情報パケットベクトル、ｐ＝（ｐ₁ ｐ₂…ｐ_m）をｍ個のパケットからなるパリティパケットベクトルとする。

例えばｋ＝７個のパケットからなる情報パケットベクトルｕからｎ＝ｋ＋ｍ＝１５個（ｎは符号化パケット数）のパケットからなる符号化パケットベクトルｖを生成する為のｋ×ｎの生成行列を

とする。このＧを用いてｖ＝ｕ・Ｇにより符号化パケットベクトルｖ＝（ｕ｜ｐ）を生成する。以後、理解を助けるために生成行列の上に符号化パケットのベクトルを記載する表現を適宜使用する。なお、空白部分は要素０を意味し、以降同様な表現を使うものとする。
また、以降０と１で表現されるＧＦ（２）上で計算するものとする。

一例としてｕ＝（１ ０ １ １ ０ １ ０）とすると下式により

となる。

一方、復号側では検査行列Ｈを用いガウス消去法等で復号する。
例えばｖに対応する誤り訂正符号のｍ×ｎのパリティ検査行列を

とする。丸付き数字は行番号を示す。このＨはＨ・ｖ^T＝０を満たす。以後、理解を助けるために検査行列の上に符号パケットのベクトルを記載する表現を適宜使用する。

今、受信機２０において受信パケット成功が符号化パケット１５パケット中９パケットの、ｕ₁，ｕ₃，ｕ₄，ｕ₆，ｕ₇，ｐ₂，ｐ₄，ｐ₅，ｐ₇とすると、ガウス消去法のステップとしてまず受信成功パケットと受信失敗のパケットの入れ替えを行う。

この問題を解決する為に従来の様な検査行列ではなく、生成行列を用いて復号計算し、（i）受信成功したパケットのみを用いて復号する手法、（ii）情報パケットの内、消失したパケットに関連する受信成功パケットのみを用いて復号する手法、（iii）受信成功したパケット数が情報パケット数×αを上限としそれ以上は復号計算対象としない手法、を提案する。

まずは（i）受信成功したパケットのみを用いて復号する手法を説明する。
［本発明の復号法１］
本発明では復号の為に（２）式に示す検査行列ではなく（１）式に示す生成行列を用いる。上記にて説明したように符号化パケットｖはｖ＝ｕ・Ｇにより生成される。さらに詳細に説明すると、パリティパケットｐ₁、ｐ₂、…、ｐ_mは、情報パケットｕ₁、ｕ₂、…、ｕ_kの一部を加算して生成されている。分かり易く説明する為に式（１）の各行に対応する情報パケットを以下の様に記述し式（３）とする。
例えばｐ₁＝ｕ₁＋ｕ₂＋ｕ₄であり、他のパリティパケットも同様に計算する。つまり、パリティパケットは情報パケットから生成できるものである為、この特性を復号に適用する。

今、受信機２０において受信成功パケットが符号化パケット１５パケット中９パケットのｕ₁，ｕ₃，ｕ₄，ｕ₆，ｕ₇，ｐ₂，ｐ₄，ｐ₅，ｐ₇とし、消失したパケットをｕ₂，ｕ₅，ｐ₁，ｐ₃，ｐ₄，ｐ₈とする。

処理の手順を説明する為に、四角枠×印を消失したパケットとして（４）式の様に生成行列Ｇを示す。

ガウス消去法のステップとして、まず受信成功パケットと消失パケットに対応する列の入れ替えを行う。

一方、ｉ列目のｉ行目に１が無かった場合、ｉ行目に１がある列とｉ列を入れ替える。その後入れ替えたｉ列目は固定して、他の列でｉ行目に１が存在する列に対し、入れ替えたｉ列を列単位で加算する。同時に列に対応する受信パケットの値も加算し新たに列に対応する値として保存する。例えば以下の様になる。

このように、実施の形態１では、受信成功したパケットのみを用い、消失したパケットを復号するためだけの計算に限定したため、少ない計算量で消失パケットを復号する事ができる。例えば、パケット誤り率ＰＥＲ（Ｐａｃｋｅｔ Ｅｒｒｏｒ Ｒａｔｅ）はＰＥＲ＝１０^-2程度を想定する事が多く、情報パケットを１００パケットとした場合でも、平均１パケット程度しか消失しないため計算量は大幅に削減する事ができる。

以上説明したように、実施の形態１の復号装置によれば、伝送路上で発生する伝送誤りを訂正するための誤り訂正符号の復号を行う復号装置において、検査行列に代えて生成行列を用いて復号する消失訂正復号部を備えたので、復号計算の計算量を削減する事ができる。

また、実施の形態１の復号装置によれば、消失訂正復号部は、受信成功したパケットとこのパケットに対応する検査行列の部分行列のみを用いて復号計算を行うようにしたので、復号計算の計算量を削減する事ができる。

また、実施の形態１の復号装置によれば、消失訂正復号部は、受信成功したパケットに対応する生成行列の列または行を並べ替えて、受信成功したパケットに対応する部分行列を構成し、消失したパケットに対応する行列に関しては削除した上で復号計算を行うようにしたので、復号計算の計算量を削減する事ができる。

実施の形態２．

そこで、更に計算量を削減する為に（ii）情報パケットの内、消失したパケットに関連する受信成功パケットのみを用いて復号する手法を実施の形態２として説明する。

［本発明の復号法２］

これに対し、本発明の復号法２では、復号法１と同様に生成行列Ｇを用いて、受信成功パケットと消失パケットを式（４）の様に対応付ける。
本発明の復号法１との違いはこの後受信成功パケットと消失パケットに対応する列の入れ替えを行わない事である。また、本発明の復号法２においては、情報パケットに対応する部分行列が対角行列になる既約標準形の生成行列を用いる必要がある。本発明の復号法２では（４）式から消失パケットに対応する列の要素を全て０にし、下記の行列Ｇ′を生成する。

このＧ′に対し列単位に行方向のガウス消去法を行う。手順としては左端から対角に計算を行い、受信成功パケットが符号化パケットの中でｉ番目のパケットの場合、ｉ列目のｉ行目に確実に１がある為、ｉ列目のｉ行目に１があるかどうかの確認を行わずに、ｉ列目は固定して他の列でｉ行目に１が存在する列に対しｉ列を列単位で加算する。同時に列に対応する受信パケットの値も加算し新たに列に対応する値として保存する。
一方、消失パケットが符号化パケットの中でｉ番目のパケットの場合、ｉ列目のｉ行目に１が無い為、ｉ列目のｉ行目に１があるかどうかの確認を行わずに、ｉ行目に１がある列とｉ列を入れ替える。その後入れ替えたｉ列目は固定して、他の列でｉ行目に１が存在する列に対し、入れ替えたｉ列を列単位で加算する。同時に列に対応する受信パケットの値も加算し新たに列に対応する値として保存する。

これを情報パケット数ｋ個分繰り返す。結果下記Ｇ″を得る。

これらの操作の本発明の復号法１との違いはｉ列目のｉ行目の１の有無を確認しない事と、受信成功パケットに対しては列の入れ替えを一切行わない事である。これによりガウス消去法における計算量が削減できる。

以上説明したように、実施の形態２の復号装置によれば、消失訂正復号部は、情報パケット部分が対角行列で構成される既約標準形の生成行列を用い、受信成功したパケットに対応する生成行列の列または行を並べ替えずに、消失パケットに対応する列要素または行要素を０にした状態でガウス消去法を行う事により、受信成功したパケットに関する計算は行わず、消失したパケットを復号するための計算のみを行うようにしたので、さらに復号計算の計算量を削減する事ができる。

実施の形態３．
次に（iii）受信成功したパケット数が情報パケット数×αを上限としそれ以上は復号計算対象としない手法を実施の形態３として説明する。
生成行列Ｇを用いる場合、情報パケットとパリティパケットの関係だけで復号出来る為、検査行列の様にＨ・ｖ^T＝０を確認する必要が無い。従って、検査行列Ｈ全体を使って符号化パケットｖ全てを計算対象にする必要は無く、十分な受信成功パケット数があれば、それ以上のパケット数は計算対象から除外してもよいという効果がある。
例えば情報パケット数５、パリティパケット数１０、符号化パケット数１５が送信機より送信され、受信機にて受信成功パケットがｕ₁，ｕ₂，ｕ₄，ｕ₅，ｐ₁，ｐ₂，ｐ₃，ｐ₅，ｐ₆，ｐ₇，ｐ₈，ｐ₉，ｐ₁₀の１３パケット、消失パケットがｕ₃，ｐ₄の２パケットとする。処理の手順を説明する為に四角枠×印を消失したパケットとして（５）式の様に生成行列Ｇを示す。

受信成功パケットに対する、計算対象の上限のパケット数をα＝２．０として情報パケット数×α＝１０個とする。この場合左から数えてｐ₇までで１０個である為、ｐ₈，ｐ₉，ｐ₁₀とそれらのパケットに対応する生成行列Ｇの列を計算対象外とする。なお、受信成功パケットがこの上限のパケット数以下の場合は全ての受信成功パケットを計算対象とする。

このような構成とする事により、情報パケットに対する符号化パケット数が多い場合でも必要最小限の計算量で復号する事が出来る。
このαの値は情報パケット数や消失誤り訂正符号の訂正能力により異なる。例えばパケット誤り率を１０^-8以下にしたいときは、図２に示す値をとるが、この数字は情報パケット数、目標性能や符号性能により適宜変更すればよく、任意の値を設定できる。

以上説明したように、実施の形態３の復号装置によれば、消失訂正復号部は、復号に必要な受信成功パケット数を情報パケット数以上で上限値を設け、上限値を超える受信成功パケットを復号計算の対象外とするようにしたので、さらに復号計算の計算量を削減する事ができる。

なお、上記の各実施の形態における説明では、生成行列、検査行列の表示方法に応じて列及び行の表現で説明してきたが、場合によっては転置した行列で表示する場合もあるので、その表示方法により列及び行の説明も対応して変化する場合もある。

また、ここまでの表現で処理単位をパケットと表現したが、パケットの名称にこだわらず、あるビットの塊で処理されるデータであれば何にでも適用でき、ブロックという呼ばれ方をする場合もある。

以上説明した符号化／復号方法は、パケット単位やブロック単位で誤り訂正する消失訂正符号以外にも、ビット単位に検査行列と対応させる物理レイヤ等の誤り訂正符号でも適用可能である。

さらに、本願発明はその発明の範囲内において、各実施の形態の自由な組み合わせ、あるいは各実施の形態の任意の構成要素の変形、もしくは各実施の形態において任意の構成要素の省略が可能である。

１０ 送信機、１１ パケット生成部、１２ 消失訂正符号化部、１３ 送信部、２０ 受信機、２１ 受信部、２２ 消失訂正復号部、２３ 情報ビット再生部、３０ 通信路。

Claims (5)

1. 伝送路上で発生する伝送誤りを訂正するための誤り訂正符号の復号を行う復号装置において、
   検査行列に代えて生成行列を用いて復号計算を行う消失訂正復号部を備えた事を特徴とする復号装置。
2. 前記消失訂正復号部は、受信成功したパケットと当該パケットに対応する検査行列の部分行列のみを用いて復号計算を行う事を特徴とする請求項１記載の復号装置。
3. 前記消失訂正復号部は、受信成功したパケットに対応する生成行列の列または行を並べ替えて、前記受信成功したパケットに対応する部分行列を構成し、消失したパケットに対応する行列に関しては削除した上で復号計算を行う事を特徴とする請求項１または請求項２記載の復号装置。
4. 前記消失訂正復号部は、情報パケット部分が対角行列で構成される既約標準形の生成行列を用い、受信成功したパケットに対応する生成行列の列または行を並べ替えずに、消失パケットに対応する列要素または行要素を０にした状態でガウス消去法を行う事により、前記受信成功したパケットに関する計算は行わず、前記消失したパケットを復号するための計算のみを行う事を特徴とする請求項１または請求項２記載の復号装置。
5. 前記消失訂正復号部は、復号に必要な受信成功パケット数を情報パケット数以上で上限値を設け、当該上限値を超える受信成功パケットを復号計算の対象外とする事を特徴とする請求項１から請求項４のうちのいずれか１項記載の復号装置。

Images