JPH04225627A - たたみ込み誤り訂正符号によって符号化されたデジタルストリームを逐次復号化する方法及び装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、たたみ込み誤り訂正符
号によって符号化されたデジタルストリーム（デジタル
系列）を逐次復号化する方法及び装置に関する。

【０００２】

【従来の技術】デジタル伝送、特にマイクロ波伝送は、
通常は非意図的な妨害である妨害をしばしば受けこれが
受信ストリームに誤りを引き起こす。このため、妨害が
あっても情報を回復するために、伝送すべきストリーム
を誤り訂正符号によって符号化しかつ誤り訂正復号器に
よって受信ストリームを復号化することが実際には重要
である。

【０００３】現在最も広まっている誤り訂正符号は、ブ
ロック符号及びたたみ込み符号である。

【０００４】ブロック符号は、より単純なものであり伝
送すべきビットの各ブロックに所定数の冗長ビットを付
加することからなる。これらブロック符号は、低い能力
の符号であり高レベルの妨害の危険を伴う通信には使用
することができない。

【０００５】たたみ込み符号ははるかに複雑であるが、
より優れた能力を有している。これらたたみ込み符号は
、伝送すべき元のストリームを実際に伝送される下記の
如きストリームに対応させる。即ちこのストリームは、
ビット数が所定係数ｎ倍（例えば２倍又は３倍）され、
先行するグループに応じてこのようにして生成されたｎ
ビットの各グループを元の各ビット毎に伴っている。

【０００６】たたみ込み符号によって符号化されたデジ
タルストリームを誤り訂正復号するために通常用いられ
る技術として以下の２つがある。

【０００７】第１の技術は、非常に多数のケースについ
て全ての可能性のあるケースを探索し、その後、最も確
率の高いものを選ぶことからなるビタビアルゴリズムを
用いるものである。このアルゴリズムは最適ではあるが
実行するには複雑である。

【０００８】第２の技術は、上述の第１の技術より最適
度は劣るが、特に複雑な符号に対して、実行するにより
単純でありかつ速度の速い「逐次復号法」を用いるもの
である。逐次アルゴリズムは、その複雑さが符号の能力
に伴って増大するものではなく、従って高い能力の符号
を復号化するのに適している。

【０００９】スタックアルゴリズム及び今は多少時代遅
れのＦＡＮＯアルゴリズムという２つのアルゴリズム及
びこれらの変形が、逐次復号化を行うのに通常は用いら
れる。　　スタックアルゴリズムにおいて、復号化はブ
ロック（例えば１０００ビットのブロック）で行われる
。 この復号化は、木の各ノードが根ノードからそこまでの
距離を表す深さによって規定されておりかつ復号化を表
している２値の「論理木」を通る「パス」を確立するこ
とからなり、該当するビットストリームについて、「メ
ータ（ｍｅｔｒｉｃ）」と称せられる数値によって規定
される確率を有している。探索されたノードは、次いで
、２つの後続するノードによってその都度延長される最
上位メータ・ノードと共に配列されたスタック内に配置
される。

【００１０】より正確には、符号化前の単一ビットに対
応する、伝送されたストリーム内の受信符号ビットの各
グループについて、スタックの最上部のノードが取り去
られ、このノードに続く２つのノードのメータが次いで
計算され、これらがそのスタック内に配置され、スタッ
クが減少するメータを有するノードによって最終的にソ
ートされる。

【００１１】スタックの規制サイズを越えた場合（即ち
スタックがオーバーフローした場合）、そのブロックは
不良に受信されたと宣言され復号されない。その後、そ
のブロックに関して再送要求がなされるかもしれないし
、失われたと見なされるかもしれない。一般的に、ブロ
ックの最大のサイズは、復号化すべきブロック内のビッ
ト数の１〜１０倍の範囲内にある。スタックが小さくな
ればなるほど復号化されないであろうブロックの数が多
くなり（スタックはしばしばオーバーフローする）、ス
タックが大きくなればなるほど非常に不良に受信された
ブロックが誤って復号化される危険を伴って復号化され
るであろうブロックの数が多くなる。

【００１２】

【発明が解決しようとする課題】スタック復号法による
主なる欠点は以下の通りである。即ち、大きなスタック
が要求されること（一般的にスタックの深さは復号化す
べきブロックのサイズの１〜１０倍の範囲内にあり、従
って１０００ビットのブロックが復号化される場合、１
０００〜１００００ビットの範囲内となる）、ノードの
メータの順位を増大させることによって行われるスタッ
クのソートが遅くなること（新しいノードがスキャンさ
れる毎に、従って復号ビットについて１〜１０倍の範囲
で、スタックがソートされねばならないにもかかわらず
）、さらに、ブロックが一度復号化されると、どのブロ
ックが実際に伝送されたのかを断定するためにトレース
バックする必要のあることである。これらの欠点により
この種の復号器は、そのサイズの点、及び速度を規制す
る復号ビットに対する多量の処理の点で実際に実現させ
ることが非常に難しい。現存する例において、スタック
はノードがスキャンされる毎にソートされるランダムア
クセスメモリ（ＲＡＭ）を用いて実現されている。

【００１３】本発明はこれらの欠点を軽減しようとする
ものであり、サイズ及び構成要素に対するコストの低減
化を図ることができかつ高速で動作できるこの種の逐次
復号器を実現可能とするものである。

【００１４】

【課題を解決するための手段】本発明によれば、たたみ
込み誤り訂正符号によって符号化されたデジタルストリ
ームを逐次復号化する方法及び装置が提供される。この
逐次復号化はスタックアルゴリズムを使用する。この方
法は漏れ性底を有するスタックを使用する（これにより
、スタックアルゴリズムによって他のノードがスタック
の最上部に入力した際、最下位メータ・ノードが失われ
る）。スタックは非常に小さいと都合が良い。ブロック
のサイズに無関係に例えば１００セル未満のスタックを
使用可能である。スタックアルゴリズムによりブロック
を復号化する間に探索したノードの総カウント数を同時
に記憶する。カウント数が前もって定められ一般的にブ
ロックのサイズの１〜１０倍の範囲にある規制値を越え
た場合、ブロックの復号化を放棄すべき表示を行う。

【００１５】

【実施例】添付図面を参照して実施例により本発明を説
明する。

【００１６】図１に示すように、たたみ込み符号を用い
て符号化された受信デジタルストリーム（受信デジタル
系列）１が、スタックアルゴリズムを使用した一般的な
逐次復号法の原理に従ってスタック２に印加される。本
発明において、スタック２は、その底３において「漏れ
性（ｌｅａｋｙ）　」を有する（即ち、他のノードが１
においてスタックの最上部に付加された際にそれに応じ
て最下位メータ・ノードがその底３から失われる）と共
に有利にはサイズが非常に小さい。このサイズは復号化
すべきブロックのサイズには全体的に無関係である。一
般的に、スタック２のサイズは１００セル未満である。 例えばスタックは４０セルで構成される。

【００１７】与えられたブロックについて、スタックア
ルゴリズムを実行して探索されたノードの総カウント数
はカウンタ４に格納される。このカウンタ４のオーバー
フロー出力５は、当該ブロックの復号化放棄の決定信号
を構成している。カウンタ４は、前もって定められてお
りかつ一般的にブロックのサイズの１〜１０倍の範囲に
ある規制値でオーバーフローする。

【００１８】最下位メータ・ノードのみが底３から失わ
れるので（各機会にスタックアルゴリズムが適用されて
スタック２がソートされかつスキャンされたノードが規
定通り８から取り去られることを伴う）、この種の装置
の性能は、探索した全てのノードを保持すると共に例え
ば１０００ビットのサイズを有する受信ブロック用に用
いられ連続する１０００〜１００００セルから構成され
たスタックを必要とする従来装置の性能に等しい。

【００１９】従来方法では、スキャンされスタック２に
入力されたノードの組は、論理木におけるこれらノード
の深さとこれらに対応する遷移（０又は＋１）と共にメ
モリ６に記憶される。偶数配列のノードが例えば０遷移
に対応し奇数配列のノードが例えば＋１遷移に対応する
と仮定すると都合が良い。これにより、ノードの２進数
の最下位ビット（ＬＳＢ）によってその遷移が与えられ
るので各ノードに対応する遷移を記憶しておく必要がな
くなる。

【００２０】さらに、木のスキャンされたパスを記憶す
る非常に小さい（例えば約１０００ビットのブロックに
ついて約１０００ビットの）他のメモリ７を用いること
が好ましい。これにより、復号化が一度終了した時に、
即ち論理ストリームの端に位置するノードがスキャンさ
れた直後に、スキャンされたパス（即ち復号化されたブ
ロック）がメモリ７から直接得られ、従って従来のごと
く、論理木にわたってトレースバックを行う必要がない
。

【００２１】最適なパスを実際に導くノードが底３から
失われてしまうという非常に低い危険性を避けるために
、３で失われるノードのメータ最大値を記憶するメモリ
９とこの失われたメータ最大値が２つの後続するノード
によって延長されるべく３１で抽出されるメータより大
きくないことを各機会毎に確認するためのコンパレータ
３０とを備えると都合が良い。３で失われるノードのこ
のメータ最大値がスタックの最上部の（３１の）メータ
より大きい場合、最適なパスが既に失われてしまった可
能性が大である。従って、出力３２でコンパレータ３０
から供給される信号は、５における信号と同様に復号化
が失敗したことを表す信号を構成する。これは、復号化
を失敗したブロックの数を僅かに増大させる。この増大
は、例えば４０より多いセルが保持されている場合に１
０−４％未満という非常に小さなものであり重大視する
ほどのものではない。

【００２２】漏れ性スタック２は、従来よりＲＡＭを用
いて当然に実現され得る。しかしながら、本発明の好ま
しい例においては、図２及び３を用いて以下説明する新
規なデジタルデータ記憶装置及び格納装置により、ソー
ト機能及び最上部のセルの内容を８から排出する機能を
伴う漏れ性スタックが実現される。

【００２３】図２に示すように、装置２は、直列に接続
され共通クロックによって同期される同一のモジュール
又はセルＭ１　、Ｍ２　、Ｍ３　、…、ＭＮ　という降
順の連続体を含んでいる。従ってこれは「収縮性の（ｓ
ｙｓｔｏｌｉｃ）」スタック、即ち全てが同時に動作す
る同一のモジュールを直列接続したものからなるスタッ
クを構成している。

【００２４】スタックの各モジュールは、前のモジュー
ルのレジスタから通常は与えられるデータ用の入力Ｅ１
　、Ｅ２　、Ｅ３　、…、ＥＮ　を有している。スタッ
クの最上部のモジュールＭ１　の入力Ｅ１　は、当然に
、このスタックに入る新データ用の入力１を構成してい
る。

【００２５】スタックの各モジュールは、さらに、その
出力データＳＮ　、…、Ｓ３　、Ｓ２　が上のモジュー
ルＭ（Ｎ−１）　、…、Ｍ２、Ｍ１　に印加される出力
レジスタを有しており、スタックの最上部のモジュール
Ｍ１　からの出力データＳ１　はこのスタックから出力
されるデータを構成している。データは、後述するよう
に、直列にかつ降順に（即ち大きい値が先に）スタック
から出力される。

【００２６】図３はモジュールＭｎ　を示している。た
だし、ｎ　は１〜Ｎ　の範囲の整数である。

【００２７】モジュールは、クロックＨによって共に同
期した２つのレジスタを有している。即ち、そのデータ
出力１０がモジュールの出力Ｓｎ　を構成している第１
のレジスタＲｍａｘ　と、そのデータ出力１１がスタッ
クの隣の下位のモジュールＭ（ｎ＋１）（図示なし）の
入力Ｅ（ｎ＋１）　を構成している第２のレジスタＲｍ
ｉｎ　とである。

【００２８】モジュールへの入力に２つのマルチプレク
サ１９及び２０が設けられている。これらのマルチプレ
クサは、それぞれの制御端子２１及び２２で受け取るＤ
Ｃ制御レベルＵ／Ｄに応答して、それぞれの出力２３及
び２４を、制御レベルＤでは右側の入力２５及び２６へ
切換え、制御レベルＵでは左側の入力２７及び２８へ切
換える。

【００２９】右側の入力２５及び２６は、隣の上位のモ
ジュールからの入力Ｅｎ　及び隣の上位のモジュール（
図２参照）にも印加されるレジスタＲｍａｘ　の出力Ｓ
ｎ　をそれぞれ受け取るように接続される。

【００３０】レジスタＲｍｉｎ　からのデータ出力１１
は隣の下位のモジュール用の入力Ｅ（ｎ＋１）　を構成
しており、さらにマルチプレクサ１９の左側の入力端子
２７への入力を構成している。マルチプレクサ２０の左
側の入力端子２８は下位のモジュールからの出力Ｓ（ｎ
＋１）　を受け取る。

【００３１】マルチプレクサ１９からの出力２３はデジ
タルコンパレータ１４の一方の入力１２と制御入力１６
がコンパレータ１４の出力信号を受け取るマルチプレク
サ１５の一方の入力１３との両方に印加される。

【００３２】コンパレータ１４の他方の入力１７とマル
チプレクサ１５の他方の入力１８との両方は、マルチプ
レクサ２０からの出力信号２４を受け取る。マルチプレ
クサ１５は、出力２３及び２４の数値のうちどちらが大
きいかを示す１６の信号に応じて、大きい方の信号がレ
ジスタＲｍａｘ　へ印加されかつ小さい方の信号がレジ
スタＲｍｉｎ　へ印加されると同時にこのレジスタＲｍ
ｉｎ　の前の内容がスタックの下位の段、即ちＭ（ｎ＋
１）　へ入力Ｅ（ｎ＋１）　を介して送られるように形
成されている。

【００３３】次にこの収縮性のスタックの動作を説明す
る。

【００３４】レベルＤの位置において、端子２６及び２
４は端子２５及び２３と同様に相互接続されており、出
力２３と出力２４とが入力１２及び１３と入力１７及び
１８とにそれぞれ印加される。

【００３５】クロックＨの１つのパルスにより、入力Ｅ
ｎ　はレジスタＲｍａｘ　の内容がこの入力Ｅｎ　より
小さい場合にこのレジスタＲｍａｘ　へ送られ、この場
合レジスタＲｍａｘの初期の内容がレジスタＲｍｉｎ　
へ送られる。入力Ｅｎ　がレジスタＲｍａｘ　の内容よ
り小さい場合は、入力Ｅｎ　はレジスタＲｍｉｎ　へ送
られる。どちらの場合にも、レジスタＲｍｉｎ　の内容
は隣の下段へ移り、この下段でも同時に同様の動作が行
われる。

【００３６】換言すれば、モジュールＭｎ　の入力に印
加される値Ｅｎ　は、このモジュールのレジスタＲｍａ
ｘ　に記憶されている値Ｓｎ　と比較される。マルチプ
レクサ１５は２つの値Ｓｎ　及びＥｎ　のうち小さい方
をレジスタＲｍｉｎ　側に切換える。２つの値のうち大
きい方はレジスタＲｍａｘ　に記憶される。レジスタＲ
ｍｉｎ　から出力される値Ｅ（ｎ＋１）　は、同時に同
じ処理が行われる隣の下位の段Ｍ（ｎ＋１）へ印加され
る。

【００３７】Ｅ１　を介してスタックの最上部に印加さ
れた値は、従って、種々の段Ｍ１　、Ｍ２　…、を介し
て前にはより小さい値を記憶していた、そのモジュール
のレジスタＲｍａｘ　に記憶されるまで、クロックＨの
速度でスタック内を累進的に下方へ移動する。次のクロ
ックパルスによって、上述のより小さい値は隣の下段へ
同じ処理で送られる。即ち、大きい方の値は止まり、小
さい方の値はスタック内のソートされた適当な位置を見
つけるまで下方へ移動する。

【００３８】逐次接続されたレジスタＲｍａｘ　によっ
て構成されたスタックは、各クロックパルス毎に自己を
自動的にソートする。新しい値Ｅ１　がこのスタックに
印加されると、必然的にそのスタックの最上部に存在す
るそのスタックの最大値と比較される。その値Ｅ１　の
方が大きい場合、その値がスタックの最上部に存在する
レジスタＲｍａｘ　に記憶される。その値Ｅ１の方が大
きくない場合、その値はスタックの隣の段に下方移動し
、新しい入力値Ｅ１　が入力１へ印加され得る。

【００３９】スタックからデータを引き出すためには、
制御レベルがＵに切換えられる。これにより、端子２３
及び２４は端子２７及び２６へそれぞれ接続される。

【００４０】これにより、クロックＨの各パルスに応じ
て、レジスタＲｍｉｎの内容が隣の下位のモジュールか
らの出力Ｓ（ｎ＋１）　と比較される。これら２つの値
のうち大きい方がレジスタＲｍａｘ　に記憶され、同時
に今までレジスタＲｍａｘ　に記憶されていた値Ｓｎ　
が同じ処理の行われる隣のモジュールへ送られる。この
ように、各クロックパルス毎に、モジュールＭｎ　の２
つの値のうち大きい方が隣の上位のモジュールＭ（ｎ−
１）　へ上方移動する。従って、スタック内の最大値が
８を介して各クロックパルス毎に出力される。即ち、そ
のスタックのデータは、直列にかつ降順にスタックから
出力される。

【００４１】本発明が上述した実施例に限定されるもの
でないことは明らかであり、また、本発明は多数の同様
な形で実施可能である。

【図面の簡単な説明】

【図１】復号化装置の動作を説明するブロック図である
。

【図２】図１の装置に用いられる漏れ性スタックの全体
ブロック図である。

【図３】図２の１つのセルをより詳しく示すブロック図
である。

【符号の説明】

Ｍ１　、Ｍ２　、Ｍ３　、…、ＭＮ　　　モジュールＲ
ｍａｘ　、Ｒｍｉｎ　　　レジスタ ２　　漏れ性スタック ４　　カウンタ ６、７　　メモリ １４、３０　　コンパレータ １５、１９、２０　　マルチプレクサ

Claims (7)

【特許請求の範囲】
1. 【請求項１】　　たたみ込み誤り訂正符号によって符号
   化されたデジタルストリームを逐次復号化する方法であ
   って、前記逐次復号化がスタックアルゴリズムを使用し
   ており、該方法が漏れ性底を有する小サイズのスタック
   を使用し、前記スタックアルゴリズムによりブロックを
   復号化する間に探索したノードの総カウント数を記憶す
   ることを含んでおり、前もって定められた規制値を越え
   た前記カウント数が該ブロックの復号化を放棄すべき表
   示を構成するようにしたことを特徴とする逐次復号化方
   法。
2. 【請求項２】　　漏れ性スタックによって論理木中の良
   好なパスを失い誤りのなだれを導くことを避けるために
   、該スタックの底から失われるノードのメータ最大値が
   、記憶されると共に該スタックの最上部にある最大メー
   タノードのメータと絶えず比較され、該比較の結果が該
   スタックの底から失われるノードのメータ最大値が該ス
   タックの最上部にあるノードのメータより大きいことを
   示す場合はブロックの復号化を放棄すべきであるとする
   ことを特徴とする請求項１に記載の逐次復号化方法。
3. 【請求項３】　　調べられたノードがそれぞれの深さ及
   び対応する遷移と共に記憶される方法であって、各ノー
   ドに対応する遷移がノード番号のＬＳＢによって構成さ
   れこれにより該遷移を記憶不要とするように、偶数番号
   ノードが第１の型の遷移（例えば０）に対応するように
   なされ、奇数番号ノードが第２の型の遷移（例えば＋１
   ）に対応するようになされることを特徴とする請求項１
   に記載の逐次復号化方法。
4. 【請求項４】　　スキャンされた論理木の端に位置する
   ノードによる復号化が終了した際、復号化されたブロッ
   クが記憶されているスキャンされたパスから直ちに得ら
   れるように、該木にわたってスキャンされたパスを記憶
   することをさらに含むことを特徴とする請求項１に記載
   の逐次復号化方法。
5. 【請求項５】　　約１００を越えないモジュールを含む
   漏れ性スタックを含むことを特徴とする請求項１に記載
   の方法を実施するための装置。
6. 【請求項６】　　前記スタックが約４０のモジュールに
   よって構成されていることを特徴とする請求項５に記載
   の装置。
7. 【請求項７】　　共通クロック信号によって同期され直
   列に接続された同一のセルによって構成された収縮性ス
   タックを使用しており、前記各セルが、前記クロック信
   号が印加される第１のレジスタと、前記クロック信号が
   また印加される第２のレジスタと、最初に前記第１のレ
   ジスタ内のデータを受け取り、次に、当該セルへの隣の
   上位のセルからの又は当該セルがスタックの最上部のセ
   ルの場合は該スタックへの外部データ入力を構成してい
   る入力デジタルデータを受け取るに適したコンパレータ
   と、２つのデータ入力を受け取り、該２つの入力値の大
   きい方を前記第１のレジスタ内のデータ値と置き換るよ
   うに該第１のレジスタへ導き、該２つの入力値の小さい
   方を前記第２のレジスタ内の値と置き換るように該第２
   のレジスタへ導き、該第２のレジスタ内にあった前記値
   が隣の下位の段へ送られてそれが入力デジタルデータを
   構成するように前記コンパレータからの出力信号によっ
   て制御されるマルチプレクサと、共通信号が第１の位置
   にある場合は、前と同様にデータを記憶しかつソートす
   るために前記データ入力及び前記第１のレジスタの内容
   を前記コンパレータへ導くに適しており、共通信号が第
   ２の位置にある場合は、各クロックパルスに応じて当該
   セル内の大きい方の値が隣の上位のセルへ上方移動し結
   果として該スタックからデータが直列にかつ降順に出力
   されるように前記第２のレジスタの内容及び隣の下位の
   セルの第１のレジスタの内容の両方を前記コンパレータ
   へ導くに適した前記共通信号によって制御される２つの
   マルチプレクサとを備えたことを特徴とする請求項５に
   記載の装置。