JPH0746778B2 - 誤り訂正方式および誤り訂正復号器 - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、伝送路上に送信データをランダム化させて送
り出す自己同期型スクランブラと受信信号を源データに
復元する自己同期型デスクランブラとが含まれている通
信システムにおける誤り訂正方式およびこの誤り訂正方
式の実施に使用される誤り訂正復号器に関する。

〔従来技術とその問題点〕

データ通信において伝送路上で生じた誤りを訂正して信
頼性の高い通信路を提供する誤り訂正技術は各方面で用
いられている。ところで、データを伝送路上に送信し、
伝送路上からデータを受信するモデムには、送信側に伝
送路上での信号がランダムになる様にするスクランブ
ラ、受信側にはそれをもとに戻すデスクランブラが組込
まれている。このスクランブラ、デスクランブラの構成
方法としては、送信側と受信側の同期を必要としない自
己同期型のスクランブラ、デスクランブラが多く用いら
れる。第３図にこの自己同期型スクランブラ、デスクラ
ンブラを含むシステムの構成を示す。図中、１は３個の
シフトレジスタ2,3,4と２個の排他的論理和回路5,6とか
ら構成される送信側の自己同期型スクランブラであり、
このスクランブラ１の伝送路側に変調器７が設けられて
いる。変調器７は、伝送路８を介して受信側の復調器９
に接続されており、この復調器９は、３個のシフトレジ
スタ10,11,12と２個の排他的論理和回路13,14とから構
成される自己同期型デスクランブラ15接続に接続されて
いる。このような自己同期型スクランブラ1,デスクラン
ブラ15を用いると同期を特にとる必要はなくなるが、伝
送路８上で生じた誤りがデスクランブラ15により拡大さ
れるという欠点がある。

第４図は、伝送路上の１ビット誤りが３ビットに拡大さ
れる状態を示す。第４図（イ）に示すようなデータ系列
が、スクランブラ１によってスクランブルされ、第４図
（ロ）に示すようなデータ系列に変換されたとする。こ
のようなデータ系列が伝送路８を介して送られる際に、
伝送路上で第４図（ハ）に示すような１ビット誤りが生
じた結果、第４図（ニ）に示すようなデータ系列が受信
側において受信される。このデータ系列が、デスクラン
ブラ15においてデスクランブルされると、第４図（ホ）
に示すようなデータ系列に復元されるが、このデスクラ
ンブル後のデータ系列を第４図（イ）のもとのデータ系
列と比較すると、第４図（ヘ）に示すように１ビットの
誤りがデスクランブルの結果３ビットの誤りに拡大され
ていることがわかる。したがって、通常の誤り訂正符号
で訂正しようとする場合には多数のビットを訂正できる
誤り訂正符号が必要となり復号のためのハードウェア規
模も大きくなり、回線の利用効率も悪くなることにな
る。

このような問題点を解決する１つの方法として、スクラ
ンブラ、デスクランブラの伝送路側に誤り訂正符号器、
復号器をそれぞれ置く方法がある。すなわち、送信側で
はスクランブラの後に符号器を置いてスクランブルした
後に符号化し、受信側ではデスクランブラの前に復号器
を置いて復号した後にデスクランブルする。このように
すればデスクランブラによる誤り拡大の影響を受けない
誤り訂正方式を実現することができる。このような方式
は、昭和53年３月の電子通信学会総合全国大会講演論文
集講演番号1634に記載されている中村，飯島の「差動符
号化用誤り訂正システム」に詳述されている。しかしな
がら、実際の伝送路においては、スクランブラ、デスク
ランブラは既にモデム内に組込まれており、利用者はこ
れを取り外したりできない状況にあることが多い。この
ような場合には、利用者はデスクランブル後の信号のみ
を観測することができ、デスクランブル前の受信信号系
列は知ることができない。従ってこのような場合にも、
やはり多数のビットを訂正できる誤り訂正符号が必要に
なり、回線の利用効率、ハードウェア規模の上で問題を
生じる。

〔発明の目的〕

本発明の目的は、このような従来の誤り訂正符号／復号
方式の欠点を取り除き、デスクランブル後の受信信号系
列とデスクランブラの生成多項式のみを知ることによっ
て、あたかもデスクランブラによる誤り拡大がなかった
かのような訂正能力を有する誤り訂正方式を提供するこ
とにある。

本発明の他の目的は、このような誤り訂正方式の実施に
使用する誤り訂正復号器を提供することにある。

〔発明の構成〕

本発明の誤り訂正方式は、伝送路上に送信データをラン
ダム化させる自己同期形スクランブラと受信信号を源デ
ータに復元する自己同期形デスクランブラとが含まれて
いる通信システムにおいて伝送路上で生じた誤りを訂正
するにあたり、 送信側では前記スクランブラの生成多項式とは互いに素
な誤り訂正生成多項式を用いて送信データにチェックビ
ットを付加してブロック符号化し、 受信側ではデスクランブルされた受信信号を前記誤り訂
正生成多項式で除算することにより各ブロックのシンド
ロームパタンを計算し、 前記シンドロームパタンを伝送路上の誤りパタンに変換
する一方、前記受信信号を遅延させたものを再スクラン
ブルして伝送路上での信号を生成し、 前記伝送路上の誤りパタンを用いて誤りを訂正した後、
再びデスクランブルして送信データを得ることを特徴と
している。

また、本発明の誤り訂正復号器は、自己同期形スクラン
ブラを含む通信システムにおいて前記スクランブラの生
成多項式と互いに素な誤り訂正生成多項式を用いて送信
データにチェックビットを付加して符号化し送信する誤
り訂正方式に用いられる誤り訂正復号器において、 デスクランブルされた受信信号を前記誤り訂正生成多項
式で除算することによりシンドロームパタンを求めるシ
ンドローム計算回路と、 前記シンドローム計算回路で得られたシンドロームパタ
ンをデスクランブル前の誤りパタンに変換するパタン変
換回路と、 前記受信信号を一時記憶するバッファメモリと、 前記バッファメモリの内容をスクランブルするスクラン
ブラと、 前記スクランブラの出力を前記パタン変換回路の出力を
用いて訂正する訂正回路と、 前記訂正回路の出力をデスクランブルするデスクランブ
ルと、 で構成され、前記デスクランブラの出力で誤り訂正復号
結果を得ることを特徴としている。

〔発明の原理〕

本発明の原理を説明するために、誤り訂正符号の生成多
項式をｇ（ｘ）、モデム内のスクランブラの生成多項式
をｆ（ｘ）、スクランブル後の符号語をｃ（ｘ）、誤り
パタンをｅ（ｘ）とそれぞれ多項式表現する。符号語ｃ
（ｘ），誤りパタンｅ（ｘ）の係数ビットパタンが、そ
れぞれ符号語のビットパタン，誤りビットパタンに相当
する。

このとき、あるブロック内で受信される信号系列ｒ
（ｘ）は、 ｒ（ｘ）＝ｃ（ｘ）＋ｅ（ｘ） ……（１） と表現できる。モデム内のデスクランブラの動作は生成
多項式ｆ（ｘ）を乗算することになるので、デスクラン
ブル後の信号系列ｕ（ｘ）は、 ｕ（ｘ）＝ｆ（ｘ）｛ｃ（ｘ）＋ｅ（ｘ）｝＝ｆ（ｘ）
ｃ（ｘ）＋ｆ（ｘ）ｅ（ｘ） ……（２） となる。ここで、ｆ（ｘ）ｃ（ｘ）は正しい符号語で、
ｆ（ｘ）ｅ（ｘ）が誤りパタンとなる。復号は通常、シ
ンドロームを求めることで行われるが、これはデスクラ
ンブル後の信号系列ｕ（ｘ）を誤り訂正符号の生成多項
式ｇ（ｘ）で割って余りｓ（ｘ）を求めることに相当す
る。すなわち余りｓ（ｘ）がシンドロームを表す多項式
表現では、 ｓ（ｘ）＝ｆ（ｘ）ｃ（ｘ）＋ｆ（ｘ）ｅ（ｘ） （mo
d g（ｘ）） ＝ｆ（ｘ）ｅ（ｘ） （mod g（ｘ）） ……（３） となる。ここで、正しい符号語ｆ（ｘ）ｃ（ｘ）は誤り
訂正符号の生成多項式ｇ（ｘ）で割り切れるので、ｆ
（ｘ）ｃ（ｘ） mod g（ｘ）は零となることを利用し
て、上式を導いている。

通常の復号法では、求められた余りｓ（ｘ）から誤りパ
タンｆ（ｘ）ｅ（ｘ）をテーブルを参照するなどして求
め、誤りパタンｆ（ｘ）ｅ（ｘ）をデスクランブル後の
信号系列ｕ（ｘ）から差し引くことで正しい符号語ｆ
（ｘ）ｅ（ｘ）を求める。但し、前述したように一般に
符号語ｆ（ｘ）ｅ（ｘ）はもとの誤りパタンｅ（ｘ）と
比較して誤りが拡大しており、誤りビット数が多いため
正しく訂正するためには、ハードウェア規模の増大をま
ねくことが多い。

これに対し本発明においてはスクランブラの生成多項式
ｆ（ｘ）と誤り訂正符号の生成多項式ｇ（ｘ）とが互い
に素である性質を利用して余りｓ（ｘ）から誤りパタン
ｅ（ｘ）を求め、デスクランブル後の信号系列ｕ（ｘ）
を再スクランブルした状態で誤りパタンｅ（ｘ）を差し
引いて訂正し、再びデスクランブルして正しい符号語ｆ
（ｘ）ｅ（ｘ）を求めるようにしている。

より詳細には、スクランブラの生成多項式ｆ（ｘ）と誤
り訂正符号の生成多項式ｇ（ｘ）とが互いに素であるこ
とから、 ｆ（ｘ）｛ｆ（ｘ）｝^-1＝１ （mod g（ｘ）） を満たす多項式｛ｆ（ｘ）｝^-1は必ず存在するから、
ｓ′（ｘ）＝｛ｆ（ｘ）｝^-1ｓ（ｘ） mod g（ｘ）……
（４） として、ｓ′（ｘ）を求める。このｓ′（ｘ）はｅ
（ｘ） mod g（ｘ）となっているので、テーブルなどを
参照してｓ′（ｘ）から誤りパタンｅ（ｘ）を求めるこ
とができる。この場合には、誤りパタンｅ（ｘ）は誤り
が拡大する以前のものであるので正しく訂正するとがで
きる。訂正するためにはスクランブル後の符号語ｃ
（ｘ）求めることが必要であるが、これはデスクランブ
ル後の信号系列ｕ（ｘ）を再スクランブルすることで得
られる。この再スクランブルは、ｕ（ｘ）/f（ｘ）＝ｃ
（ｘ）＋ｅ（ｘ）＋ｉ（ｘ） ……（５） と表現される。ここで、ｉ（ｘ）は本発明の誤り訂正復
号器内のスクランブラの初期値に対応して現れる不確定
項であるが、本発明の誤り訂正復号器内のデスクランブ
ラで同じ初期値によりデスクランブルすることで除くこ
とができる。従って、 ｕ（ｘ）/f（ｘ）−ｅ（ｘ）＝ｃ（ｘ）＋ｉ（ｘ）……
（６） をデスクランブルすることにより正しい符号語ｆ（ｘ）
ｃ（ｘ）を得ることができる。

〔実施例〕

第１図は、本発明の誤り訂正方式の一実施例を示すフロ
ーチャートである。この誤り訂正方式は、伝送路上に送
信データをランダム化させる自己同期形スクランブラと
受信信号を源データに復元する自己同期形デスクランブ
ラとが含まれている通信システムにおいて用いられる。

まず、スクランブラの生成多項式ｆ（ｘ）とは互いに素
な生成多項式ｇ（ｘ）を用いて送信データに誤り訂正符
号（チェックビット）を付加してブロック符号化する
（ステップS1）。ブロック符号化された信号は、スクラ
ンブラにおいてチェックビットの生成多項式ｇ（ｘ）と
は互いに素な生成多項式ｆ（ｘ）を用いてスクランブル
され（ステップS2）、伝送路に送出される（ステップS
3）。受信側では、受信した信号ｒ（ｘ）を、デスクラ
ンブラにおいてデスクランブルする（ステップS4）。デ
スクランブルされた受信信号ｕ（ｘ）から各ブロックの
シンドロームパタンｓ（ｘ）を計算し（ステップS5）、
計算されたシンドロームパタンｓ（ｘ）を、伝送路上の
誤りパタンｅ（ｘ）に変換する（ステップS6）。一方、
デスクランブルされた受信信号ｕ（ｘ）を遅延させ（ス
テップS7）、遅延させた受信信号を再スクランブルして
伝送路上での信号を生成する（ステップS8）。このよう
にして生成された伝送路上での信号を、ステップS6にお
いて求められた伝送路上の誤りパタンを用いて誤り訂正
し（ステップS9）、再びデスクランブルして送信データ
を得ている（ステップS10）。

次に、以上の誤り訂正方式の実施に用いることのできる
誤り訂正復号器の実施例を第２図に基づいて説明する。
この誤り訂正複号器は、デスクランブルされた受信信号
ｕ（ｘ）を一時記憶するバッファメモリ17と、このバッ
ファメモリ17の内容をスクランブルするスクランブラ20
と、デスクランブルされた受信信号ｕ（ｘ）からシンド
ロームパタンｓ（ｘ）を求めるシンドローム計算回路18
と、このシンドローム計算回路18で得られたシンドロー
ムパタンをデスクランブル前の誤りパタンに変換するパ
タン変換回路19と、スクランブラ20の出力をパタン変換
回路19の出力を用いて訂正する訂正回路21と、この訂正
回路21の出力を再びデスクランブルするデスクランブラ
22とから構成されている。なお、シンドローム計算回路
18の例は、昭晃堂発行のコンピュータ基礎講座第18巻
「符号理論」宮川，岩重，今井の309ページに記載され
ている。

このような構成の誤り訂正復号器において、入力端子16
にはデスクランブルされた受信信号ｕ（ｘ）が入力され
る。入力信号は、バッファメモリ17に入力されて一時記
憶されると同時に、シンドローム計算回路18にも入力さ
れシンドロームパタンｓ（ｘ）が求められる。シンドロ
ーム計算回路18で求められたシンドロームパタンｓ
（ｘ）は、パタン変換回路19で伝送路上の誤りパタンｅ
（ｘ）に変換される。これはシンドローム計算回路18と
同様に、ｓ（ｘ）/f（ｘ） mod g（ｘ）を計算し変換テ
ーブルで誤りパタンｅ（ｘ）にすることもできるし、シ
ンドロームパタンｓ（ｘ）から直接誤りパタンｅ（ｘ）
に変換することもできる。

一方、バッファメモリ17に蓄えられた受信信号ｕ（ｘ）
は、スクランブラ20でスクランブルされる。スクランブ
ラ20の出力をパタン変換回路19の出力を用いて訂正回路
21で逐次訂正する。訂正回路における訂正は、スクラン
ブラ20とパタン変換回路19の出力の排他的論理和をとる
ことで実現される。訂正回路出力はデスクランブラ22で
デスクランブルされ、正しい符号語が端子23から出力さ
れる。

なお、本発明では符号語単位に訂正を行うので符号語の
終りの方で誤りが発生し、それが次の符号語に伝播する
ような場合には正しく訂正することができないが、符号
語の長さがスクランブラの長さよりも十分長いときには
このような誤りは無視することができる。

〔発明の効果〕

以上説明したように本発明によれば、スクランブラ、デ
スクランブラが存在するような伝送路において、デスク
ランブラによる誤り拡大の影響を受けないような誤り訂
正方式およびデスクランブラによる誤り拡大の影響を受
けることなく誤り訂正および復号のできる誤り訂正復号
器を提供することができる。

【図面の簡単な説明】

第１図は、本発明の誤り訂正方式の一実施例を説明する
ためのフローチャートを示す図、 第２図は、本発明の誤り訂正復号器の一実施例を示す
図、 第３図は、スクランブラ、デスクランブラを含む伝送シ
ステムの例を示す図、 第４図は、デスクランブラによる誤り拡大の状態を示す
図である。 17……バッファメモリ 18……シンドローム計算回路 19……パタン変換回路 20……スクランブラ 21……訂正回路 22……デスクランブラ

Claims (2)

【特許請求の範囲】
1. 【請求項１】伝送路上に送信データをランダム化させる
   自己同期形スクランブラと受信信号を源データに復元す
   る自己同期形デスクランブラとが含まれている通信シス
   テムにおいて伝送路上で生じた誤りを訂正するにあた
   り、 送信側では前記スクランブラの生成多項式とは互いに素
   な誤り訂正生成多項式を用いて送信データにチェックビ
   ットを付加してブロック符号化し、 受信側ではデスクランブルされた受信信号を前記誤り訂
   正生成多項式で除算することにより各ブロックのシンド
   ロームパタンを計算し、 前記シンドロームパタンを伝送路上の誤りパタンに変換
   する一方、前記受信信号を遅延させたものを再スクラン
   ブルして伝送路上での信号を生成し、 前記伝送路上の誤りパタンを用いて誤りを訂正した後、
   再びデスクランブルして送信データを得ることを特徴と
   する誤り訂正方式。
2. 【請求項２】自己同期形スクランブラを含む通信システ
   ムにおいて前記スクランブラの生成多項式と互いに素な
   誤り訂正生成多項式を用いて送信データにチェックビッ
   トを付加して符号化し送信する誤り訂正方式に用いられ
   る誤り訂正復号器において、 デスクランブルされた受信信号を前記誤り訂正生成多項
   式で除算することによりシンドロームパタンを求めるシ
   ンドローム計算回路と、 前記シンドローム計算回路で得られたシンドロームパタ
   ンをデスクランブル前の誤りパタンに変換するパタン変
   換回路と、 前記受信信号を一時記憶するバッファメモリと、 前記バッファメモリの内容をスクランブルするスクラン
   ブラと、 前記スクランブラの出力を前記パタン変換回路の出力を
   用いて訂正する訂正回路と、 前記訂正回路の出力をデスクランブルするデスクランブ
   ルと、 で構成され、前記デスクランブラの出力で誤り訂正復号
   結果を得ることを特徴とする誤り訂正復号器。