JPH0740672B2 - ビツトシリアル誤り訂正復号化装置 - Google Patents

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明はディジタルデータの伝送あるいは蓄積などによ
ってデータに生じた誤りを自動的に訂正する誤り訂正復
号化装置に関するものである。

（従来の技術） ディジタルデータの伝送あるいは蓄積などによって生じ
る誤りは、伝送路上の雑音あるいは蓄積媒体の物理的な
欠陥によるものが多いことが認められている。従来、そ
のような雑音や欠陥の影響から逃れるために、データを
送る側ではデータをいくつかの情報シンボルに区切り、
各シンボルに対して予め決められた順序でもって変換を
施し冗長度を付加してから、伝送路上あるいは蓄積媒体
に送り出し、データを受ける側では、伝送路あるいは蓄
積媒体から送られてきた受信信号系列に含まれる前記冗
長度をもとにして、各シンボルの誤りを検出し訂正する
という方式を採用している。

情報シンボルに変換を施し冗長ビット列を付加する方法
および変換されて冗長ビット列の付加された受信信号列
からもとの情報シンボルを復元する方法として従来一般
によく知られ利用されているものに、それぞれ畳み込み
符号やトレリス符号などの木符号を用いる方法及び逐次
復号アルゴリズムを用いる方法がある。本発明は一般的
な木符号と逐次復号アルゴリズムについて適用できる
が、以下では説明の都合上、木符号については畳み込み
符号と呼ばれる符号に限定し、逐次復号アルゴリズムに
ついてはファノアルゴリズムと呼ばれるアルゴリズムに
限定して説明を行う。木符号及び逐次復号アルゴリズム
についての詳細は例えば、（株）昭晃堂から1973年に発
行された刊行物「符号理論」に詳しく述べられている。
なお、ファノアルゴリズムは米国人ファノ（R.M.Fano）
が考案したもので、1963年に米国電気電子工学会の情報
理論に関する論文誌の第９巻64〜74項（IEEE Transacti
on on Information Theory,IT−9,pp.64−74）に「ア
ヒューリスチック デスカッションオブ プロバブリス
チック デ コーディグ（A Heuristic Discussion of
Probabilistic Deconding）」という題名で掲載された
論文の中で述べられている。

これらの方法のうち情報シンボルに変換を施し冗長ビッ
ト列を付加する方法については簡潔に述べれば、誤り訂
正符号化装置（以下では端に符号器ともいう）は、例え
ばシフトレジスタのような、内部状態を保持するための
回路を持ち、入力される情報シンボルに依存して、予め
決められた方法で内部状態を変更する。内部状態を保持
する回路としてシフトレジスタを用いている場合には、
情報シンボルをシフトレジスタに入力することによって
内部状態を変更する。一方、符号器は、内部状態を予め
決められた関数発生器に入力して冗長ビット列を発生
し、その冗長ビット列を符号シンボルに付加したものを
符号シンボルとする。符号器から出力された符号シンボ
ルは伝送路を通って、あるいは蓄積媒体に一旦記録・再
生された後、復号器に送られる。復号器の受け取ったア
ナログ受信信号をディジタル化して得られる受信信号
は、伝送路上の雑音あるいは蓄積媒体の物理的な欠陥に
よって生じた誤りにより、必ずしも送られた符号ビット
とは一致しない。

受信信号列から情報を逐次復号アルゴリズムによって復
元する方法について簡単に述べれば、誤り訂正復号化装
置（以下では単に復号器ともいう）は、対応する符号器
と同一の機能を有する回路（以下では符号器複製とい
う）を内部に持っており、例えば情報シンボルの長さが
２ビットならば00、01、10、11の４通りのすべての可能
なビット列を符号器複製にそれぞれ入力したときの符号
器複製の出力ビット列を受信信号列とそれぞれ比較し
て、受信信号列に最も近い符号シンボルを与える情報シ
ンボルを送られた情報シンボルだと推定する。近さの尺
度としては、一般に、次式で定義されるファノ尤度と呼
ばれる尤度が用いられる。

λ＝log₂｛ｐ（y|x）/p（ｙ）｝−Ｂ ここでｐ（ｙ）は受信信号がｙである確率を、ｐ（y|
x）は符号ビットｘが送られた下で復号器が受信信号ｙ
を受け取る確率である。また、Ｂはバイアスと呼ばれる
固有な値で予めシミュレーションなどによって最適な値
を決めておく。なお、ファノ尤度は実数値であるが、実
際には装置化の都合上ファノ尤度にほぼ比例した整数値
で近似したものを用いる。ファノアルゴリズムでは、基
本的には、ファノ尤度の累積尤度が最も大きくなる情報
シンボル列を送られた情報シンボル列だと判定してゆ
く。もっとも、伝送路上の雑音が強いときには、受信信
号に誤りが多発し、間違った情報シンボルを送られた情
報シンボルだと判定してしまう可能性があるのだが、も
し復号器が一旦誤った判定をした場合には、それ以後の
復号器複製の内部状態が符号器の内部状態と食い違い、
それ以後は復号器がファノ尤度の大きな情報シンボルを
見つけようとしてもなかなか見つからなくなるので、過
去において誤った判定を行ったことが検出できる。従っ
て、逐次復号アルゴリズムでは、復号器がファノ尤度の
大きな情報シンボルを見つけにくくなると、過去におい
て誤った判定を行ったと判定して、符号器複製の内部状
態を過去の状態に戻した後、過去において選んだ情報シ
ンボルの次にファノ尤度の大きな情報シンボルを送られ
た情報シンボルだと判定して復号化をやり直す。ただ
し、次に大きな情報シンボルを見つけ出そうとしても、
すでに探索済みで、見つけることができなければ、もう
一つ過去の状態に戻って同様の操作を行う。復号器が過
去において誤った判定を行ったと判断する厳密な基準に
ついては前記文献に述べられている。なお、逐次復号ア
ルゴリズムでは、そのような施行錯誤を繰り返して復号
化を行うために、一旦出力した復号結果が後で変更され
る可能性があるから、復号器の復号結果を装置の外部に
出力するときにはバッファを介して行う必要がある。

なお、ファノアルゴリズムでは、一つの情報シンボルの
ビット表現が長くなって探索すべき情報シンボルの種類
が多くなると、ファノ尤度を比較する手数が多くなり実
用的でない。例えば情報シンボルの長さが１ビットであ
れば０と１の２通りの情報シンボルのファノ尤度を比較
すればよいが、情報シンボルの長さが８ビットであると
256通りもの情報シンボルの尤度を比較しなければなら
ない。このため実際には、一般に、尤度の大小を比較せ
ずに予め決められた優先順位で強制的に送られた情報シ
ンボルを選んで行く方法が用いられる。例えば情報シン
ボルの長さが２ビットのときには、まず00が送られた情
報シンボルだと仮定し、その仮定が不確かそうなら次に
01,10,11という順序で情報シンボルを選んでゆく。この
方法は米国人ガラガー（Robert G.Gallager）が考案し
たファノアルゴリズムの改良版で、詳細は1968年に米国
でジョン ワイレイ アンド サンズ（株）（John Wil
ey ＆ Sons,Inc）から出版されたガラガー著「インフォ
メーション セオリー アンド リライアブル コミュ
ニケーション（Information Theory and Reliable Comm
unication）」に示されている。以下ではガラガーの方
法をガラガーの改良ファノアルゴリズムと呼ぶ。

もっとも、ガラガーの改良ファノアルゴリズムでは、正
しいと仮定した情報シンボルがどの程度受信信号列に近
いかを無視して予め固定された優先順位で情報シンボル
を選んでゆくために、最初に正しいと仮定した情報シン
ボルが正しくないという場合が多いので、情報シンボル
を修正する手数が多くなる。そこで実際には、組織符号
やクイックルックイン符号と呼ばれる特殊な符号が用い
られる。組織符号というのは、情報シンボルにパリティ
を付け加えて符号シンボルを構成する符号であるから、
受信信号から直接にある程度正確に情報シンボルを推定
することができる。したがって予め決められた順序では
なく、受信信号から直接に推定された情報シンボルに近
いものから順に選んでゆけば、送られた可能性の高い情
報シンボルから順に選んでゆけるので後で情報シンボル
を修正する手数が少なくて済む。なお組織符号以外の符
号は非組織符号と呼ばれる。クイックルックイン符号と
いう符号は非組織符号であるが、組織符号とほぼ同様、
受信信号と過去の受信信号の最上位ビットとのビットご
との排他的論理和をとることによって、受信信号から情
報シンボルを簡単に推定することができるものである。
ただし、組織符号やクイックルックイン符号は符号の構
造が制限されるため一般の非組織符号に比べて誤り訂正
能力が低い。

さて、上記のような情報シンボルの符号化及び復号化を
実行するための誤り訂正符号化装置及び誤り訂正復号化
装置は、例えば米国人ジョージ・デビット・フォーニィ
ジュニア（George David Forney Jr.）の米国特許第3,6
65,396に記されているような回路で実現できる。

（発明が解決しようとする問題点） しかしながら従来のフォノアルゴリズムを採用した誤り
訂正復号化装置では、すべての可能な情報シンボルのう
ちでファノ尤度の最も大きなシンボルを送られた情報シ
ンボルと判定していたので、情報シンボルのビット表現
が長くなると可能な情報シンボルの数が多くなり、ファ
ノ尤度が最大となる情報シンボルを求めるための演算量
が増大してしまう。例えば、情報シンボルの長さが１ビ
ットであれば可能な情報シンボルは０、１の２通りしか
ないので１回の比較演算で情報シンボルの判定が行える
が、情報シンボルの長さが３ビットになると可能な情報
シンボルは000,001,…111の８通りもあるので情報シン
ボルの判定には少なくとも７（＝８−１）回の比較演算
が必要となる。また従来のガラガーの改良ファノアルゴ
リズムを採用した誤り訂正装置で非組織符号を扱おうと
すると、情報シンボルのファノ尤度によらず予め固定し
た順序で判定を行うので、情報シンボルのビット表現が
長いときには間違った情報シンボルを送信された情報シ
ンボルであると間違って判定してしまうことが多く、例
えば情報シンボルの長さが３ビットのときには受信信号
に誤りが無い場合でも正しい情報シンボルを選ぶまでに
平均４（＝8/2）回程度間違った情報シンボル送信され
た情報シンボルであると判定してしまう。すなわち、従
来の誤り訂正装置では、情報シンボルのビット表現が長
くなると高速な復号化が実行出来ないという欠点があっ
た。

ところがコンピュータと通信とが融合したシステムによ
って構築される今日の情報化社会においては、大量の情
報を誤りなくかつ高速に伝送することが要求される。

本発明の目的は従来の誤り訂正復号化装置の上記欠点を
取除き、情報シンボルのビット表現が長くなっても高速
な復号化が実行できるような誤り訂正装置を提供するこ
とにある。

（問題点を解決するための手段） 本発明は、順に入力されてくる情報シンボルを状態保持
回路に保持し、状態保持回路の内部状態を関数発生器に
入力して得られた冗長ビットを情報シンボルに付加して
これを符号シンボルとして出力する符号化率（ｎ−１）
/nの誤り訂正符号化装置に対応する誤り訂正復号化装置
において、前記誤り訂正符号化装置の関数発生器と等価
な関数発生器と、前記誤り訂正符号化装置のn/（ｎ−
１）倍のビットを保持し、保持されたビットのうちｎビ
ットごとにｎ−１ビットを関数発生器に供給する、双方
向シフト可能な状態保持回路と、入力される符号ビット
と受信信号に従ってファノアルゴリズムを実行する符号
化率1/1の逐次復号制御回路と、逐次復号制御回路が状
態保持回路を右にシフトすると、新しい受信信号を状態
保持回路の左端と逐次復号制御回路に供給し、逐次復号
制御回路が状態保持回路を左にシフトすると、古い受信
信号を逐次復号制御回路に供給するとともに状態保持回
路が保持していた過去のビットを状態保持回路の右端に
供給するバッファと、逐次復号制御回路が状態保持回路
を右にシフトすると増やされ、逐次復号制御回路が状態
保持回路を左にシフトすると減じられるｎビットカウン
タと、ｎビットカウンタの出力が予め決められた値と等
しいか否かを判定する識別器と、識別器の出力に従っ
て、状態保持回路の左端に保持された情報ビットと、関
数発生器の出力のいずれかを選択して、そのビットを符
号ビットとして逐次復号制御回路に供給するセレクタと
を具備し、前記符号化率（ｎ−１）/nの誤り訂正装置が
出力した符号シンボル系列に対応する受信信号から、元
の情報シンボル系列をビット単位の処理によって復元す
るようにしたものである。

（作用） 従来から広く利用されている畳み込み符号のような木符
号では情報シンボルのビット長は情報シンボルの位置に
依らず一定である。ところが、情報シンボルのビット長
が一定でないような符号に対しても、ファノアルゴリズ
ムなどの従来から用いられてきた復号化法を利用して復
号を行うことは原理的には可能である。もっとも、情報
シンボルのビット長が一定でないような符号では一般に
符号化の際に情報１ビット当たりに付加される冗長ビッ
トの数が情報ビットの位置に依って異なる結果、誤り訂
正能力も情報ビットの位置によって異なってしまう。こ
のため、データ伝送のようにどの情報ビットにも等しい
誤り訂正能力が必要な用途では、情報シンボルのビット
長が一定でないような符号は利用されなかった。これに
対して本発明の基本的な原理は、符号器において情報シ
ンボルのビット長が一定であるような符号を用いるもの
の、復号器においてはその符号をそれと等価で情報シン
ボルのビット長が一定でないような符号と見なして復号
化するところにある。もし、情報シンボルのビット長が
一定であるような符号をその符号と等価で情報シンボル
のビット長が一定でないような符号と見なすことが可能
で、しかもその等価の符号の情報シンボルのビット長が
もとの符号のビット長よりも小さければ、情報シンボル
のビット長が一定でないような符号と見なして復号化す
ることによって、情報ビットを１ビット復号するのにつ
き必要な比較演算の回数を少なくできるので従来方式よ
りも高速に復号化することが可能となる。

もっともこの方法は全て木符号に対して適用できるわけ
ではないが、少なくとも工学的に重要な組織符号には適
用できる。組織符号とは、既に述べたように情報シンボ
ルのビット表現に冗長ビットあるいは冗長ビット列を付
加して符号シンボルを構成する符号である。組織符号で
は、仮に情報シンボルのビット長をｋビットとし符号シ
ンボルのビット長をｎビットとすれば、情報シンボルの
ｋビットの各々のビットが符号器に入力される毎に符号
シンボルのビット表現が１ビットずつ確定して行き、情
報シンボルの全てのビットが入力された後に符号シンボ
ルの残りｎ−ｋ個のビット表現が確定するので、この符
号は、符号シンボルの最初のｋビットの部分については
それぞれ長さ１ビットの情報シンボルに対して長さ１ビ
ットの符号シンボルを出力し、残りのｎ−ｋビットの部
分についてはそれぞれ長さ０ビットの情報シンボルに対
して長さ１ビットの符号シンボルを出力する符号と見な
すことができる。ファノアルゴリズムで前者の符号を復
号する場合には、復号操作を１回行う毎に2k通りの情報
シンボルに対して尤度を計算してそれらの尤度を比較す
るために2^k−１回の比較演算を行う必要があったのに対
して、後者の符号を復号する場合には、復号操作を１回
行う毎に２通りの情報シンボルに対して尤度を計算して
それらの尤度を比較するために１回の比較演算を行えば
十分である。前者の復号化法では情報ビット１ビット当
たり必要な比較演算の回数は（2^k−１）/k回であるのに
対して、後者の復号化法では情報ビット１ビット当たり
必要な比較演算の回数はわずか１回であるから、ｋが大
きいときには情報シンボルのビット長が一定でないよう
な符号と見なして復号化することによって、復号化が高
速化されるわけである。

以上述べたことを具体例で示せば次のようになる。例え
ば、長さ２ビットの情報シンボルに１ビットの冗長シン
ボルを付加して長さ３ビット符号シンボルを構成するよ
うな組織符号の符号器の場合には、情報シンボルの２ビ
ットの各々のビットが符号器に入力される毎に符号シン
ボルビット表現が１ビットずつ確定して行き、情報シン
ボルのすべてのビットが入力された後に符号シンボルの
残り１個のビット表現が確定するので、この符号は、符
号シンボルの最初の２ビットの部分についてはそれぞれ
長さ１ビットの情報シンボルに対して長さ１ビットの符
号シンボルを出力し、残りの１ビットの部分については
長さ０ビットの情報シンボルに対して長さ１ビットの符
号シンボルを出力する符号とも見なすことができる。フ
ァノアルゴリズムで前者の符号を復号する場合には、復
号操作を１回行う毎に４通りの情報シンボルに対して尤
度を計算してそれらの尤度を比較するために３（＝４−
１）回の比較演算を行う必要があったのに対して、後者
の符号を復号する場合には、復号操作を１回行う毎に２
通りの情報シンボルに対して尤度を計算してそれらの尤
度を比較するために１（＝２−１）回の比較演算を行え
ば十分である。前者の復号化法では情報ビット１ビット
当たり必要な比較演算の回数は1.5（＝3/2）回であった
のに、後者の復号化法では情報ビット１ビット当たり必
要な比較演算の回数は１（＝（１＋１＋０）/2）回であ
る。情報シンボルのビット長ｋが２ビット程度でも、情
報シンボルのビット長が一定でないような符号と見なし
て復号化することによって、復号化がかなり高速化され
ることがわかる。

なお、本発明は従来の復号器に比べて高速な復号速度を
実現するものであるが、そのためには符号器複製に特殊
な機能を付け加えるだけでよく、復号器の本体は従来用
いられていたものと同一の装置が利用できるので実現は
容易である。すなわち、本発明では情報シンボルの長さ
が高々１ビットの符号として復号化するから、情報シン
ボルのビット長が１ビットの符号に対して従来用いられ
ていた復号器がそのまま利用できる。情報シンボルのビ
ット長が１ビットで符号シンボルのビット長が２ビット
であるような符号に対する復号器は、例えば米国人ジョ
ージ・デビット・フォーニィジュニア（George David F
orney,Jr.）の米国特許第3,665,396に記されているよう
な回路で実現できる。ただし、本発明では情報シンボル
の長さは、符号シンボルの各ビットが情報ビットに対応
するかあるいは冗長ビットに対応するかによって１であ
ったり０であったりして一定でないから、符号シンボル
の各ビットが情報ビットに対応するかあるいは冗長ビッ
トに対応するかを示す識別器が必要である。

第１図に本発明の基本構成を示す。また第２図に第１図
の復号器に対応する符号器の基本構成を示す。以下では
情報シンボルの長さをｎ−１ビットとし符号シンボルの
長さをｎビットとする。便宜上第２図の符号器から説明
する。第２図の符号器において、入力端子から201から
１ビットずつ順に入力されてくる情報ビットはシリアル
パラレル変換器205でシリアルパラレル変換を受けて長
さｎ−１ビットの情報シンボルに変換された後、状態保
持回路202に保持されてゆき、保持された情報シンボル
によって状態保持回路202の内部状態を更新してゆく。
内部状態保持回路202には一般にシフトレジスタをｎ−
１段並列に並べたものが用いられ、情報シンボルが入力
されるごとに、シフトレジスタの内容が１ビットずつ右
にシフトされてシフトレジスタ202の左端に新しい情報
シンボルが保持される。一方、状態保持回路202の内部
状態は関数発生器203の入力供給されており、情報シン
ボルが入力されるたびに関数発生器203は冗長ビットを
出力し、情報シンボルと共に合計ｎビットが符号シンボ
ルとして出力されて、パラレルシリアル変換器206でパ
ラレルシリアル変換を受けた後に１ビットづつ出力端子
204から伝送あるいは蓄積の目的で出力されてゆく。た
だし伝送のために多値変調を行う場合にはパラレルシリ
アル変換は不要である。

次に第１図の復号器について説明する。従来の復号器と
同一部分については略記する。第１図の復号器におい
て、状態保持回路102、関数発生器103は対応する第２図
の符号器が具備しているものとほぼ同一機能のものであ
る。ただし、状態保持回路102は、復号化の過程で過去
の状態に戻す必要があるので、内部状態を可逆的に変更
できるような機能が付加されている。例えば状態保持回
路102をシフトレジスタで構成する場合には双方向シフ
トレジスタが用いられる。また、すでに述べたように本
発明では、ビットごとにシリアルに入力された情報シン
ボルのビット表現に対して符号シンボルのビット表現を
ビットごとにシリアルに出力する機能を第２図の符号器
に付加した符号器複製を用いるが、このために第２図の
状態保持回路202がｎ−１段パラレルであったのに対し
て第１図の状態保持回路102では１段シリアル構成にな
っている。また、第２図の符号器では状態保持回路には
情報ビットのみが保持されたが、状態保持回路102では
冗長ビットに対応してダミーのビットも保持するので、
状態保持回路102の保持するビット数は第２図の状態保
持回路の保持するビット数のn/（ｎ−１）倍である。

さらに本発明では従来の復号器で情報シンボルのビット
長が１であるものと異なり、情報シンボルのビット長が
符号シンボル位置によって一定でないため、ただ単に情
報シンボルのビット表現を符号器複製にシリアル入力す
るだけでは不十分である。というのも、符号シンボルの
位置によって情報シンボルのビット長が、１であったり
０であったりして一定でないからである。符号器複製の
出力をビット毎にシリアルに得る場合には、情報シンボ
ルのビット長が１の時には状態保持回路102に入力され
た情報ビットの推定値を符号ビットとして出力し、一
方、情報シンボルのビット長が０の時には状態保持回路
102に入力された情報ビットでなく関数発生器103の出力
する冗長ビットを符号ビットとして出力する必要があ
る。このため、情報シンボルの長さをｎ−１ビットとし
符号シンボルの長さをｎビットとすれば、モジュロｎの
ｎ進カウンタ105と識別器106とセレクタ107を付加す
る。カウンタ105は状態保持回路102の内容がそれぞれ左
右にシフトされる毎に１だけ増減される。識別器106は
カウンタ105が予め決められた値を取ると１それ以外の
時は０を出力する。セレクタ110は識別器106の出０の時
には状態保持回路102の左端に保持されたビットを選択
し、選択器106の出力が１の時には関数発生器103の出力
するビットを選択する。そして逐次復号制御回路115
が、セレクタ110の出力とレジスタ112に保持された受信
信号を比較してファノアルゴリズムを実行する。逐次復
号制御回路115はファノアルゴリズムに従って状態保持
回路102の内容を左右にシフトしたり状態保持回路102の
左端に反転器109の出力を保持したりする。この逐次復
号制御回路115の構造は、逐次復号制御回路105に入力さ
れるビット数が従来のものより少ないという点を除け
ば、従来のものと同一である。

第１図における信号の動きは次の通りである。アナログ
受信信号をA/D変換して得られた受信信号は、入力端子1
01から入力されて一旦入力バッファ111に蓄えられ、逐
次復号制御回路115が必要とするときにレジスタ112と状
態保持回路102の左端に保持される。逐次復号制御回路1
15は過去の推定が正しいと判断しているときには、状態
保持回路102の内容を右にシフトしはみ出したビットを
バッファ114に出力すると同時に、レジスタ112の受信信
号をバッファ113に出力し、バッファ111から受信信号を
取り出しその受信信号をレジスタ112に、受信信号の最
上位ビットを状態保持回路102の左端に保持する。一
方、逐次復号制御回路115が過去の推定は間違っている
と判断して復号器の状態を過去の状態に戻す時には、逐
次復号制御回路115は状態保持回路102を左にシフトし、
バッファ114から過去にバッファ114に入力されたビツト
を取り出し状態保持回路102の右端に保持すると同時
に、レジスタ112の受信信号をバッフア111に戻して、バ
ッファ113から過去にバッファ113に入力された受信信号
を取り出してレジスタ112に保持する。すなわち状態保
持回路102の内容を左右にシフトさせる制御信号は、カ
ウンタ105を増減するために使うのと同時に、バッファ1
11,113,114及びレジスタ112の内容を左右に移動させる
のにも使用される。また、逐次復号制御回路115が過去
に状態保持回路に入力したビットが送信された情報ビッ
トでないと判定して、その値を修正する時には、反転器
109で状態保持回路102の左端に保持されたビットの値を
反転して再び状態保持回路102の左端に保持し直す。た
だし常に修正が可能なわけでなく、すでに修正を行った
場合と識別器106の出力が１の場合には修正できない。
修正が出来ない場合には、逐次復号制御回路はさらに過
去の判定を修正する。修正が可能かどうかを示す信号は
過去に修正が行われたかを調べるための排他的論理和回
路107の出力と識別器106の出力を論理和回路108に入力
することによって生成する。状態保持回路102を右に動
かしてその左端に新しく推定した情報ビットを保持した
時にはその左端にはレジスタ112に保持された受信信号
の硬判定と同じ値が保持されているのに対して、修正を
行った後では両者は異なった値になっているから、状態
保持回路102の左端に保持されたビットレジスタとレジ
スタ112に保持された受信信号の硬判定との排他的論理
和を排他的論理和回路107によってとることで過去に修
正が行われたかどうかが判る。逐次復号制御回路が以上
の操作を行って行けば、次第にバッファ114に情報ビッ
トの推定値すなわち復号結果が蓄えられて行き、復号結
果は最終的に出力端子104から出力されて行く。

以上述べたような基本構成を用いて、情報シンボルの尤
度をビット単位に求めて逐次的に情報シンボルのビット
表現を推定してゆけば、結果的に、すべての情報シンボ
ルの全てのビットについて尤度を計算することなく、尤
度の大きな情報シンボルを選び出すことができる。

（実施例） 第３図に本発明の一実施例を示す。また第４図に第３図
の復号器に対応する符号器の一実施例を示す。以下では
情報シンボルの長さを３ビットとし符号シンボル長さを
４ビットとする。第３図及び第４図においてそれぞれ第
１図及び第２図と同一の機能を有する部分には同一の番
号を付して示す。便宜上第４図の符号器から説明する。
第４図の符号器において、入力端子201から１ビットず
つ順に入力されてくる情報ビットはシリアルパラレル変
換器205でシリアルパラレル変換を受けて長さ３ビット
の情報シンボルに変換された後、状態保持回路202に保
持されてゆき、保持された情報シンボルによって状態保
持回路202の内部状態を更新してゆく。内部状態保持回
路202にはそれぞれ長さ３ビットのシフトレジスタ407,4
08,409を３段並列に並べたものが用いられ、情報シンボ
ルが入力されるごとに、シフトレジスタの内容が１ビッ
トずつ右にシフトされてシフトレジスタ202の左端に新
しい情報シンボルが保持される。一方、状態保持回路20
2の内部状態は関数発生器203の入力に供給されており、
情報シンボル入力されるたびに関数発生器203は冗長ビ
ットを出力し、情報シンボルと共に合計４ビットが符号
シンボルとして出力されて、パラレルシリアル変換器20
6でパラレルシリアル変換を受けた後に１ビットづつ出
力端子204から伝送あるいは蓄積の目的で出力されてゆ
く。なお、関数発生器203は排他的論理和回路401,402,4
03,404,405,406によつて構成されており、状態保持回路
202に保持されているビットのうち排他的論理和回路40
1,402,403の入力端子へ供給されているビットの奇パリ
ティを発生する。

次に第３図の復号器について説明する。従来の復号器と
同一部分については略記する。第３図の復号器におい
て、状態保持回路102、関数発生器103は対応する第４図
の符号器が具備しているものとほぼ同一機能のものであ
る。ただし、状態保持回路102は、復号化の過程で過去
の状態に戻す必要があるので、内部状態を可逆的に変更
できるような機能が付加されている。すなわち状態保持
回路102は双方向シフトレジスタで構成される。また、
すでに述べたように本発明では、ビットごとにシリアル
に入力された情報シンボルのビット表現に対して符号シ
ンボルのビット表現をビットごとにシリアルに出力する
機能を第４図の符号器に付加した符号器複製を用いる
が、このために第４図の状態保持回路202が３段パラレ
ルであったのに対して第３図の状態保持回路102では１
段シリアル構成になっている。また、第４図の符号器で
は状態保持回路には情報ビットのみが保持されたが、状
態保持回路102では冗長ビット対応してダミーのビット
も保持するので、状態保持回路102の保持するビット数
は第２図の状態保持回路の保持するビット数の4/3倍す
なわち12（３×３×（4/3）ビットである。

さらに本発明では従来の復号器で情報シンボルのビット
長が１であるものと異なり、情報シンボルのビット長が
符号シンボルの位置によって一定でないため、ただ単に
情報シンボルのビット表現を符号器複製にシリアル入力
するだけでは不十分である。というのも、符号シンボル
の位置によって情報シンボルのビット長が、１であった
り０であったりして一定でないからである。符号器複製
の出力をビット毎にシリアルに得る場合には、情報シン
ボルのビット長が１の時には状態保持回路102に入力さ
れた情報ビットの推定値を符号ビットとして出力し、一
方、情報シンボルのビット長が０の時には状態保持回路
102に入力された情報ビットでなく関数発生器103の出力
する冗長ビットを符号ビットとして出力する必要があ
る。符号シンボルの長さが４ビットであるから、モジュ
ロ４の４進カウンタ105と識別器106とセレクタ107を付
加する。モジュロ４の４進カウンタとは長さ２ビットの
二進カウンタに他ならない。カウンタ105は状態保持回
路102の内容がそれぞれ左右にシフトされる毎に１だけ
増減される。識別器106はカウンタ105がオール０にある
と１それ以外の時は０を出力する。セレクタ110は識別
器106の出力が０の時には状態保持回路102の左端に保持
されたビットを選択し、識別器106の出力が１の時には
関数発生器103の出力するビットを選択する。そして逐
次信号制御回路115が、セレクタ110の出力とレジスタ11
2に保持された受信信号を比較してファノアルゴリズム
を実行する。逐次復号制御回路115はファノアルゴリズ
ムに従って状態保持回路102の内容を左右にシフトした
り状態保持回路102の左端に反転器109の出力を保持した
りする。この逐次復号制御回路115の構造は、逐次復号
制御回路105に入力されるビット数が従来のものより少
ないという点を除けば、従来のものと同一である。な
お、本実施例では関数発生器103は第４図の関数発生器2
03と同様、排他的論理和回路301,302,303,304,305,306
によって構成されており、状態保持回路102に保持され
ているビットのうち排他的論理和回路301,302,303の入
力端子へ供給されているビットの奇パリティを発生す
る。

第３図における信号の動きは次の通りである。アナログ
受信信号をA/D変換して得られた２ビットの受信信号
は、入力端子101から入力されて一旦入力バッファ111に
蓄えられ、逐次復号制御回路115が必要とするときにレ
ジスタ112と状態保持回路102に左端に保持される。逐次
復号制御115は過去の推定が正しいと判断しているとき
には、状態保持回路102の内容を右にシフトしはみ出し
たビットをバッファ114に出力すると同時に、レジスタ1
12の受信信号をバッファ113に出力し、バッファ111から
受信信号を取り出しその受信信号をレジスタ112に、受
信信号の上位ビットを状態保持回路102の左端に保持す
る。一方、逐次復号制御回路115が過去の推定は間違っ
ていると判断して復号器の状態を過去の状態に戻す時に
は、逐次復号制御回路115は状態保持回路102を左にシフ
トし、バッファ114から過去にバッフア114に入力された
ビットを取り出し状態保持回路102の右端に保持すると
同時に、レジスタ112の受信信号をバッファ111に戻し
て、バッファ113から過去にバッファ113に入力された受
信信号を取り出してレジスタ112に保持する。すなわち
状態保持回路102の内容を左右にシフトさせる制御信号
は、カウンタ105を減増するために使うのと同時に、バ
ッファ111,113,114及びレジスタ112の内容を左右に移動
させるのにも使用される。また、逐次復号制御回路115
が過去に状態保持回路に入力したビットが送信された情
報ビットでないと判定して、その値を修正する時には、
反転器109で状態保持回路102の左端に保持されたビット
の値を反転して再び状態保持回路102の左端に保持し直
す。ただし常に修正が可能なわけでなく、すでに修正を
行った場合と識別器106の出力が１の場合には修正は出
来ない。修正が出来ない場合には、逐次復号制御回路は
さらに過去の判定を修正する。修正が可能かどうかを示
す信号は過去に修正が行われたか調べるための排他的論
理和回路107の出力と識別器106の出力を論理和回路108
に入力することによって生成する。状態保持回路102を
右に動かしてその左端に新しく推定した情報ビットを保
持した時にはその左端にはレジスタ112に保持された受
信信号の硬判定と保持されてのに対して、修正を行った
後では両者は異なった値になっているから、状態保持回
路102の左端に保持されたビットとレジスタ112に保持さ
れた受信信号の硬判定との排他的論理和回路を排他的論
理和回路107によってとることで過去に修正が行われた
かどうかが判る。逐次復号制御回路が以上の操作を行っ
て行けば、次第にバッファ114に情報ビットの推定値す
なわち復号結果が蓄えられて行き、復号結果は最終的に
出力端子104から出力されて行く。

（発明の効果） 以上述べてきたように、本発明に従えば、情報シンボル
のビット長が長くなっても高速な復号化が実行できるよ
うな誤り訂正装置が容易に構成できる。

従って本発明がコンピュータと通信とが融合したシステ
ムによって構築される今後の情報化社会において、伝送
あるいは蓄積などによって生じる誤りからデータを保護
する目的で効果を発揮できることは明らかである。

【図面の簡単な説明】

第１図は本発明の基本構成図、第２図は第１図の復号器
に対応する符号器の基本構成、第３図は本発明の一実施
例、第４図は第３図の復号器に対応する符号器の実施例
を示す図である。図において 101,201……入力端子、 102,202……状態保持回路、 103,203……関数発生器、 104,204……出力端子、 105……カウンタ、106……識別器、 107……排他的論理和回路、 108……論理和回路、109……反転器、 110……セレクタ、 111,113,114……バッファ、 112……レジスタ、 205……シリアルパラレル変換器 206……パラレルシリアル変換器 301,302,303,304,305,306……排他的論理和回路、 401,402,403,404,405,406……排他的論理和回路、 407,408,409……双方向シフトレジスタ

Claims (1)

【特許請求の範囲】
1. 【請求項１】順に入力されてくる情報シンボルを状態保
   持回路に保持し、状態保持回路の内部状態を関数発生器
   に入力して得られた冗長ビットを情報シンボルに付加し
   てこれを符号シンボルとして出力する符号化率（ｎ−
   １）/nの誤り訂正符号化装置に対応する誤り訂正復号化
   装置において、 前記誤り訂正符号化装置の関数発生器と等価な関数発生
   器と、前記誤り訂正符号化装置のn/（ｎ−１）倍のビッ
   トを保持し、保持されたビットのうちｎビットごとにｎ
   −１ビットを関数発生器に供給する、双方向シフト可能
   な状態保持回路と、入力される符号ビットと受信信号に
   従ってファノアルゴリズムを実行する符号化率1/1の逐
   次復号制御回路と、逐次復号制御回路が状態保持回路を
   右にシフトすると、新しい受信信号を状態保持回路の左
   端と逐次復号制御回路に供給し、逐次復号制御回路が状
   態保持回路を左にシフトすると、古い受信信号を逐次復
   号制御回路に供給するとともに状態保持回路が保持して
   いた過去のビットを状態保持回路の右端に供給するバッ
   ファと、逐次復号制御回路が状態保持回路を右にシフト
   すると増やされ、逐次復号制御回路が状態保持回路を左
   にシフトすると減じられるｎビットカウンタと、ｎビッ
   トカウンタの出力が予め決められた値と等しいか否かを
   判定する識別器と、識別器の出力に従って、状態保持回
   路の左端に保持された情報ビットと、関数発生器の出力
   のいずれかを選択して、そのビットを符号ビットとして
   逐次復号制御回路に供給するセレクタとを具備し、前記
   符号化率（ｎ−１）/nの誤り訂正装置が出力した符号シ
   ンボル系列に対応する受信信号から、元の情報シンボル
   系列をビット単位の処理によって復元することを特徴と
   する誤り訂正復号化装置。