(57)【特許請求の範囲】
【請求項１】
ディジタル通信の伝送路符号の送受信装置であって、
シリアル通信のデータの中へのクロックの埋め込み、ＤＣバランシング、伝送中に発生するビット誤りの検出機能の内包、及び前記ビット誤りの訂正機能の内包、の全てを一度に行う符号化手段と、
前記符号化手段で符号化された符号語を送信する送信手段と、
受信した前記符号語について、前記ビット誤りの検出、及び前記ビット誤りの訂正を行う復号手段と
を備え、
前記符号化手段は、変換テーブルを用いて、ＣビットのデータをＤビットのビット列の前記符号語に変換し、
前記変換テーブルは、前記各符号語のＤビットのビット列において連続する０または１はＥビット以下であり、前記各符号語のビット列において０と１とは同数であり、前記各符号語のビット列の任意の１ビットを反転させて得られるビット列において連続する０または１はＥビット以下であり、前記各符号語のビット列同士においてハミング距離はＦ以上であり（Ｆ≦Ｅ）、
前記復号手段は、受信した前記符号語と前記変換テーブルの全ての前記各符号語のビット列とのハミング距離を算出し、算出した前記ハミング距離が最小となる符号語のビット列を前記変換テーブル内から選択し、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離が０の場合には伝送中のビット誤りは発生していないと判断して対応するCビットの前記データに復号し、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離がＭの場合には伝送中にＭビットの誤りが発生したと判断してビット誤りを訂正して対応するCビットの前記データに復号し（１≦Ｍ）、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離がＮ以上の場合には伝送中にＮビット以上の誤りが発生したと判断してビット誤りを検出する（Ｍ＜Ｎ）ことを特徴とするディジタル通信の伝送路符号の送受信装置。
【請求項２】
ディジタル通信の伝送路符号の送受信装置であって、
シリアル通信のデータの中へのクロックの埋め込み、ＤＣバランシング、伝送中に発生するビット誤りの検出機能の内包、及び前記ビット誤りの訂正機能の内包、の全てを一度に行う符号化手段と、
前記符号化手段で符号化された符号語を送信する送信手段と、
受信した前記符号語について、前記ビット誤りの検出、及び前記ビット誤りの訂正を行う復号手段と
を備え、
前記符号化手段は、変換テーブルを用いて、４ビットのデータを１０ビットのビット列の前記符号語に変換し、
前記変換テーブルは、前記各符号語の１０ビットのビット列において連続する０または１は５ビット以下であり、前記各符号語のビット列において０と１とは同数であり、前記各符号語のビット列の任意の１ビットを反転させて得られるビット列において連続する０または１は５ビット以下であり、前記各符号語のビット列同士においてハミング距離は４以上であり、
前記復号手段は、受信した前記符号語と前記変換テーブルの全ての前記各符号語のビット列とのハミング距離を算出し、算出した前記ハミング距離が最小となる符号語のビット列を前記変換テーブル内から選択し、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離が０の場合には伝送中のビット誤りは発生していないと判断して対応する４ビットの前記データに復号し、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離が１の場合には伝送中に１ビットの誤りが発生したと判断してビット誤りを訂正して対応する４ビットの前記データに復号し、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離が２以上の場合には伝送中に２ビット以上の誤りが発生したと判断してビット誤りを検出することを特徴とするディジタル通信の伝送路符号の送受信装置。
【請求項３】
前記変換テーブルは、表１で表されることを特徴とする請求項２に記載のディジタル通信の伝送路符号の送受信装置。
【表１】
0005900850.tif 000002
【請求項４】
ディジタル通信の伝送路符号の送受信方法であって、
各符号語のＤビットのビット列において連続する０または１はＥビット以下であり、前記各符号語のビット列において０と１とは同数であり、前記各符号語のビット列の任意の１ビットを反転させて得られるビット列において連続する０または１はＥビット以下であり、前記各符号語のビット列同士においてハミング距離はＦ以上である（Ｆ≦Ｅ）変換テーブルを生成するステップと、
前記変換テーブルを用いて、ＣビットのデータをＤビットのビット列の符号語に変換するステップと、
変換した前記符号語を送信するステップと、
受信した前記符号語と前記変換テーブルの全ての前記各符号語のビット列とのハミング距離を算出するステップと、
算出した前記ハミング距離が最小となる符号語のビット列を前記変換テーブル内から選択するステップと、
受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離が０の場合には伝送中のビット誤りは発生していないと判断して対応するCビットの前記データに復号し、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離がＭの場合には伝送中にＭビットの誤りが発生したと判断してビット誤りを訂正して対応するCビットの前記データに復号し（１≦Ｍ）、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離がＮ以上の場合には伝送中にＮビット以上の誤りが発生したと判断してビット誤りを検出する（Ｍ＜Ｎ）ステップと
を備えることを特徴とするディジタル通信の伝送路符号の送受信方法。
【請求項５】
ディジタル通信の伝送路符号の送受信方法であって、
各符号語の１０ビットのビット列において連続する０または１は５ビット以下であり、前記各符号語のビット列において０と１とは同数であり、前記各符号語のビット列の任意の１ビットを反転させて得られるビット列において連続する０または１は５ビット以下であり、前記各符号語のビット列同士においてハミング距離は４以上である変換テーブルを生成するステップと、
前記変換テーブルを用いて、４ビットのデータを１０ビットのビット列の符号語に変換するステップと、
変換した前記符号語を送信するステップと、
受信した前記符号語と前記変換テーブルの全ての前記各符号語のビット列とのハミング距離を算出するステップと、
算出した前記ハミング距離が最小となる符号語のビット列を前記変換テーブル内から選択するステップと、
受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離が０の場合には伝送中のビット誤りは発生していないと判断して対応する４ビットの前記データに復号し、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離が１の場合には伝送中に１ビットの誤りが発生したと判断してビット誤りを訂正して対応する４ビットの前記データに復号し、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離が２以上の場合には伝送中に２ビット以上の誤りが発生したと判断してビット誤りを検出するステップと
を備えることを特徴とするディジタル通信の伝送路符号の送受信方法。
【請求項６】
前記変換テーブルは、表２で表されることを特徴とする請求項５に記載のディジタル通信の伝送路符号の送受信方法。
【表２】
0005900850.tif 000003
【請求項７】
請求項２若しくは請求項３に記載のディジタル通信の伝送路符号の送受信装置、又は請求項５若しくは請求項６に記載のディジタル通信の伝送路符号の送受信方法に用いる符号の生成方法であって、
それぞれの前記符号語を、
１０ビット内で０と１とを同数とし、
前記符号語内の任意の１ビットを反転させて得られるビット列において、連続する０または１を５ビット以下とし、
２つの前記符号語を連結して得られる２０ビットのビット列内の任意の１ビットを反転させて得られるビット列において、連続する０または１を５ビット以下とし、
ハミング距離を４以上とし、
２つの前記符号語を連結して得られる２０ビットの前記ビット列内の任意の２ビットを反転させて得られるビット列において、連続する０または１を５ビット以下、ただし、２つの前記符号語を連結して得られる２０ビットの前記ビット列内の一方の前記符号語内の任意の１ビットを反転させるとともに、他方の前記符号語内の任意の１ビットを反転させたときに、２つの反転ビット同士が４ビット以上離れているもの
として生成することを特徴とする符号の生成方法。
【請求項８】
請求項１に記載のディジタル通信の伝送路符号の送受信装置、又は請求項４に記載のディジタル通信の伝送路符号の送受信方法に用いる符号の生成方法であって、
Cビットの送信データをDビットの符号語に変化する場合において、
それぞれの前記符号語を、
符号語Dビット内で０と１とを同数とし、
前記符号語内の任意の１ビットを反転させて得られるビット列において、連続する０または１を指定ビット（Eビット）以下とし、
２つの前記符号語を連結して得られる２倍のDビットのビット列内の任意の１ビットを反転させて得られるビット列において、連続する０または１をEビット以下とし、
ハミング距離を指定する数F以上とし（F≦E）、
２つの前記符号語を連結して得られる２倍のDビットの前記ビット列内の任意の２ビットを反転させて得られるビット列において、連続する０または１をEビット以下、ただし、２つの前記符号語を連結して得られる２倍のDビットの前記ビット列内の一方の前記符号語内の任意の１ビットを反転させるとともに、他方の前記符号語内の任意の１ビットを反転させたときに、２つの反転ビット同士がFビット以上離れているもの
として生成することを特徴とする符号の生成方法。
【請求項９】
請求項４から請求項６のいずれかに記載のディジタル通信の伝送路符号の送受信方法の全ステップをコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特に、シリアル通信においてデータにクロックを埋め込んで送信するエンベデッドクロック方式に関し、さらに、ディジタル通信の符号化に関わり、より詳細には、伝送路符号、誤り検出符号、誤り訂正符号に関するものである。
【背景技術】
【０００２】
ディジタル通信では、伝送周波数の高速化に伴い、データにクロックを埋め込んで送信するエンベデッドクロック方式を用いた高速シリアル通信への要求が高まっている。エンベデッドクロック方式を用いた実用的な高速シリアル通信を実現するためには、送信信号のＤＣバランシング（０と１を同程度にする方法）を確保するための伝送路符号が必要となる。伝送路符号の実例として、「Ｂｙｔｅ  Ｏｒｉｅｎｔｅｄ  ＤＣ  Ｂａｌａｎｃｅｄ（０，４）８Ｂ１０Ｂ  Ｐａｒｔｉｔｉｏｎ  Ｂｌｏｃｋ  Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｄｅ」と題する、ＦｒａｎａｓｚｅｋおよびＷｉｄｍｅｒによる米国特許第４，４８６，７３９号に記載の８Ｂ１０Ｂ伝送コードがＰＣＩ  ＥｘｐｒｅｓｓやＩｎｆｉｎｉＢａｎｄなどの通信規格で採用されている。
【０００３】
さらに、現代のディジタル通信においては、伝送路でのエラー検出やエラー訂正は必須の機能となっている。例えば、ＰＣＩ  Ｅｘｐｒｅｓｓでは、ＣＲＣを用いてデータリンクレイヤでエラー検出を行っている。受信側でエラーが検出された場合、送信側にシーケンスナンバと共にＮＡＫ（Ｎｏｔ  Ａｃｋｎｏｗｌｅｄｇｅ）を返すことで、送信側が再送を行う。
【０００４】
信頼性のない伝送路では、伝送中に発生するビット誤りを検出、および訂正する必要がある。誤り検出符号、および誤り訂正符号を用いることで、伝送中に発生するビット誤りを検出、および訂正が可能である。誤り検出符号、および誤り訂正符号の実例として、ハミング符号（非特許文献１）や、ＢＣＨ符号（非特許文献２）などがある。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｒ．Ｗ．Ｈａｍｍｉｎｇ；Ｅｒｒｏｒ  Ｄｅｔｅｃｔｉｎｇ  ａｎｄ  Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｎｇ  Ｃｏｄｅｓ，  Ｂｅｌｌ  Ｓｙｓｔｅｍ  Ｔｅｃｈｎｉｃａｌ  Ｊｏｕｒｎａｌ，  Ｖｏｌ．２９，  ｐｐ．１４７−１６０（１９５０）
【非特許文献２】Ｒ．Ｃ．Ｂｏｓｅ  ａｎｄ  Ｄ．Ｋ．Ｒａｙ−Ｃｈａｕｄｈｕｒｉ；Ｏｎ  Ａ  Ｃｌａｓｓ  ｏｆ  Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｎｇ  Ｂｉｎａｒｙ  Ｇｒｏｕｐ  Ｃｏｄｅｓ，  Ｉｎｆｏｒｍａｔｉｏｎ  ａｎｄ  Ｃｏｎｔｒｏｌ  ３，  Ｖｏｌ．１，  ｐｐ．６８−７９（１９６０）
【発明の開示】
【発明が解決しようとする課題】
【０００６】
エンベデッドクロック方式で用いられる伝送路符号では、ＤＣバランシングを確保するために伝送データをより長いビット列に符号化するという特性上、伝送中に発生するビット誤りが、復号後により大きな誤りとなる場合がある。（以下、元データを符号化したデータ（ビット列）を符号語と呼称する。）例えば伝送中にビット誤りが発生し、正しい符号語からハミング距離が１離れたとすると、誤った符号語を復号した結果、復号されたデータは正しいデータからハミング距離が１以上離れる可能性がある。この結果、復号後の誤り検出、および訂正のコストが非常に高くなる。８Ｂ１０Ｂ伝送コードのようなエンべデッドクロック方式でエラー訂正を同時に行いたい場合には、ビット単位でのエラー訂正は用いることが困難であり、リードソロモン符号のようなブロックエラー訂正符号をパケット単位（大きなブロック単位）で後段に行う必要がある。この場合には、パケットをすべて受信しきらないとエラー訂正を行うことができず、レイテンシが長くなり、リアルタイム通信等には不向きとなる。
ここで、近年、ヒューマノイドロボット等の複雑なリアルタイムシステムの出現により、単一プロセッサで行う処理の限界や、システムの耐故障性等を向上するために、プロセッサを複数用いた分散リアルタイムシステムへの要求が高まっている。
分散リアルタイムシステムでは、ノード内の処理においてリアルタイム性を満たすだけでなく、ノード間の通信においてもリアルタイム性を保証しなければならない。このような背景から、分散リアルタイムシステムのための通信機構としてレスポンシブリンク（Ｒｅｓｐｏｎｓｉｖｅ  Ｌｉｎｋ）が国内外で標準化されている。具体的には、レスポンシブリンクは、国内ではIPSJ-TS 0006として、国際的にはISO/IEC 24740として標準化されている。
【０００７】
従って、本発明の目的は、エンベデッドクロック方式の伝送路符号に、DCバランシング、誤り検出および誤り訂正機能を内包することで、誤り検出および誤り訂正を同時に実現することにある。具体的には、従来手法では不可能であった、データにクロックを埋め込んで通信、ＤＣバランシング、エラー検出機能、エラー訂正機能、を一つの符号で同時に行う。エラー検出及びエラー訂正機能付きのエンべデッドクロック方式の伝送路符号化を実現することで、信頼性が高くレイテンシも短いシリアルデータ通信を実現する。
【課題を解決するための手段】
【０００８】
本発明によるディジタル通信の伝送路符号の変換方法は、ディジタル通信の伝送路符号の変換方法であって、シリアル通信のデータの中にクロックを埋め込み、前記クロックの埋め込みの際にＤＣバランシングを行い、前記データと前記クロックの転送を同じ配線で行うことが可能な符号化手段と、前記符号化手段で符号化された符号語について、伝送中に発生するビット誤りの検出を行う誤り検出手段と、前記誤り検出手段で検出された前記ビット誤りの訂正を行う誤り訂正手段とを備えたことを特徴とする。
また、本発明によるディジタル通信の伝送路符号の一例（以下、４B10B符号と称す）を以下に示す。前記符号化手段では、変換テーブルを用いて４ビットの送信データを１０ビットの前記符号語に変換し、ＤＣバランシングを実現しつつ、データ内にクロックを埋め込む。
また、本発明によるディジタル通信の伝送路符号の一つである４B１０B符号では、それぞれの前記符号語は、連続する０または１が５ビット以下であることを特徴とし、伝送中に発生する１０ビット中１ビット以内のビット誤りが発生してもエンベデッドクロックを維持できる。
また、本発明によるディジタル通信の伝送路符号の一つである４B１０B符号では、それぞれの前記符号語は、前記符号化した各ビット列同士のハミング距離が４以上であり、前記誤り検出手段では、１０ビット中２ビット以内のビット誤りの検出を行うことを特徴とする。
また、本発明によるディジタル通信の伝送路符号の一つである4B10B符号では、前記誤り訂正手段では、１０ビット中１ビットのビット誤りの訂正を行うことを特徴とする。
また、本発明によるディジタル通信の伝送路符号の一つである４B10B符号化を行う符号の生成方法は、それぞれの前記符号語を、１０ビット内で０と１とを同数とし、前記符号語内の任意の１ビットを反転させて得られるビット列において、連続する０または１を５ビット以下とし、２つの前記符号語を連結して得られる２０ビットのビット列内の任意の１ビットを反転させて得られるビット列において、連続する０または１を５ビット以下とし、ハミング距離を４以上とし、２つの前記符号語を連結して得られる２０ビットの前記ビット列内の任意の２ビットを反転させて得られるビット列において、連続する０または１を５ビット以下とし、２つの前記符号語を連結して得られる２０ビットの前記ビット列内の一方の前記符号語内の任意の１ビットを反転させるとともに他方の前記符号語内の任意の１ビットを反転させたときに、２つの反転ビット同士を４ビット以上として生成することを特徴とする。
また、本発明によるディジタル通信の伝送路符号の変換方法を行う符号の生成方法は、それぞれの前記符号語を、１０ビット内で０と１とを同数とし、前記符号語内の任意の１ビットを反転させて得られるビット列において、連続する０または１を５ビット以下とし、
２つの前記符号語を連結して得られる２０ビットのビット列内の任意の１ビットを反転させて得られるビット列において、連続する０または１を５ビット以下とし、ハミング距離を４以上とし、２つの前記符号語を連結して得られる２０ビットの前記ビット列内の任意の２ビットを反転させて得られるビット列において、連続する０または１を５ビット以下とし、２つの前記符号語を連結して得られる２０ビットの前記ビット列内の一方の前記符号語内の任意の１ビットを反転させるとともに他方の前記符号語内の任意の１ビットを反転させたときに、２つの反転ビット同士を４ビット以上として生成することを特徴とする。
【発明の効果】
【０００９】
本発明によれば、ラインコード自体にエラー検出機能とエラー訂正機能の両方を持たせて信頼性の高い通信を実現することができる。
【図面の簡単な説明】
【００１０】
【図１】本発明による４Ｂ１０Ｂ符号を示す変換テーブル
【図２】本発明によるビット誤りによるハミング距離と、誤り検出、および誤り訂正の概要を示す図
【図３】本発明によるデコードのフローチャート
【発明を実施するための形態】
【００１１】
本発明に従った符号化（４Ｂ１０Ｂ符号化）を、図１に示す変換テーブルを用いて例示する。図１では、４ビットの元データを１０ビットのデータ（符号語）へ変換することで、元データ内にクロックを埋め込み、ＤＣバランシング（０と１の割合をまったく同じにする）を実現し、１０ビットのデータ中の２ビットの誤りを検出し、１０ビットのデータ中の１ビットの誤り訂正をするという各機能を同時に実現する。
【００１２】
図１に示す変換テーブルによれば、符号化した１０ビットの各ビット列において連続する０または１は必ず５ビット以下になるようにしつつ、クロックを埋め込んでいる。さらには、この符号語内で任意の１ビットが反転しても連続する０または１は５ビット以下になるようにしている。例えば、符号語が「１１００１１００１０」であったとした場合、符号語内の一つの任意の「１」に誤りが生じて「０」に反転した場合であっても、連続するビットは５ビット以下となる。
同様に、任意の符号化した１０ビットと別の符号化した１０ビットの符号語間においても連続する０または１は必ず５ビット以下になるようにしている。この結合部分においても任意の１ビットが反転しても連続する０または１は５ビット以下になるようにしている。したがって、各符号語で誤りがある場合は誤りビット同士が４ビット以上離れているときに不連続性を保証する。例えば、２つの符号語が、「１１００１１００１０」と「１００１１１０００１」であった場合、「１１００１１００１０」が「１１００１１００００」となり、「１００１１１０００１」が「１０００１１０００１」となっても、２つの誤りビットが４ビット以上離れていれば、連続するビットは５ビット以下となる。
【００１３】
図１に示す変換テーブルによれば、符号化した１０ビットの符号語内の０と１の数を必ず同数になるようにし、ＤＣバランシングを実現する。
【００１４】
図１に示す変換テーブルによれば、符号化した１０ビットの各ビット列同士のハミング距離は４以上離れており、伝送中に発生する１０ビット中１ビットの誤りは、正しいビット列が一意に決まるため、誤りの訂正が可能である。ビット誤りによるハミング距離と、誤り検出、および誤り訂正の概要を図２に示す。
【００１５】
本発明に従えば、符号化を行う符号器は図１に示した変換テーブルに基づき、４ビットのデータから１０ビットの符号語を生成する。復号化を行う復号器は、入力された１０ビットの符号語を図１に示した変換テーブルの全てのビット列とのハミング距離を求め、変換テーブル内でハミング距離が最も小さいものが選択され、復号される。最も小さいハミング距離が０だった場合、伝送中のビット誤りは存在せず、正しく復号化される。ハミング距離が１だった場合、伝送中に１ビットの誤りが発生したことになり、誤りは訂正されて正しく復号化される。ハミング距離が２以上だった場合、伝送中に２ビット以上の誤りが発生したことになり、誤りは検出できるが、訂正はできない。１０ビット中２ビットまでの誤りを検出することができる。図３に復号のフローを示す。
【００１６】
図１に示す４Ｂ１０Ｂ符号化変換テーブルを生成するアルゴリズムを以下に示す。
操作１．１０ビットの符号語から以下の条件１、２、３をすべて満たすものだけを抽出し、この集合をＳＯとする。
条件１．１０ビット内で０と１が同数である。
条件２．符号語内の任意のビットを１ビット反転させて得られるビット列において、連続する０または１が５ビット以下である。
条件３．符号自身を２つ連結して得られる２０ビットのビット列内の任意のビットを１ビット反転させて得られるビット列において、連続する０または１が５ビット以下である。
操作２．ＳＯの各符号語について、ＳＯ中の他の符号語すべてに対して、それぞれ、以下の条件４、５のすべてを満たす符号数をカウントする。
条件４．ハミング距離が４以上である。
条件５．２つの符号語ＡとＢを連結して得られる２０ビットの２つのビット列（ＡＢとＢＡ）の任意のビットを最大２ビット反転させて得られるビット列において、連続する０または１が５ビット以下である。ただし、２ビット反転する際は反転ビットは符号語Ａに１ビット、Ｂに１ビットかつ２つの反転ビット同士が４ビット以上離れているものとする。
操作３．ＳＯの中で操作２によって得られたカウント数Ｎが１６以上のものだけを抽出し、この集合をＳ１とする。
操作４．同様に操作２と操作３を集合の要素数が収束するまで繰り返す。最終的に得られた集合をＳｃとする。
操作５．Ｓｃを操作２によって得られたカウント数について昇順にソートし、順に配列Ｓに格納する。
操作６．配列の最初の要素Ｓ［０］から順に一つずつ符号語を取り出し、集合Ｓｔの要素として加える。ただし、Ｓｔは初め空集合であり、また加える符号語はＳｔの全符号語に対して、条件４と条件５すべてを満たす必要があり、条件を満たさない符号語はＳｔに加えない。
操作７．操作６によって得られたＳｔをＳｍａｘとし、その要素数をＭとする。
操作８．同様にＳ［１］から順に操作６を行い、Ｓｔの要素数がＭを上回れば、ＳｍａｘおよびＭを更新する。
操作９．操作８を配列Ｓの最後まで同様に繰り返す。
操作１０．Ｓｍａｘが４Ｂ１０Ｂ符号化の符号空間となる（ＭがＮ（＝１６）以上となっている）。  
【００１７】
このアルゴリズムにより、データ内にクロックを埋め込み（連続する０または１は５ビット以下）、ＤＣバランシング（符号化後の１０ビット中の０と１が同数）、１０ビット中２ビットの誤り検出、１０ビット中１ビットの誤り訂正の各機能を同時に実現するように、４ビットのデータを１０ビットのデータ（符号語）へ変換する符号を見つけることができる。
【００１８】
伝送路符号としてよく使用される８Ｂ１０ＢやＮＲＺＩ（Ｎｏｎ  Ｒｅｔｕｒｎ  ｔｏ  Ｚｅｒｏ  Ｉｎｖｅｒｔｅｄ）＋Ｂｉｔ  Ｓｔａｆｆｉｎｇ等の符号では、伝送路上のデータ１ビットが化けた場合でも、復号後に複数ビットのエラーとして検出される場合があるが、本発明によれば、復号時には伝送されてきた１０ビットをテーブル内から検索し、ハミング距離が１以内のものはエラーが訂正され正しく復号される。
【００１９】
より一般的にCビットの元データをDビットの符号語に変換する変換テーブルを生成するアルゴリズムを以下に示す（C＜D）。
操作１．Dビットの符号語から以下の条件１、２、３をすべて満たすものだけを抽出し、この集合をＳＯとする。
条件１．Dビット内で０と１が同数である。
条件２．符号語内の任意のビットを１ビット反転させて得られるビット列において、連続する０または１が指定ビット（Eビット）以下である。
条件３．符号自身を２つ連結して得られる２倍のDビットのビット列内の任意のビットを１ビット反転させて得られるビット列において、連続する０または１がEビット以下である。
操作２．ＳＯの各符号語について、ＳＯ中の他の符号語すべてに対して、それぞれ、以下の条件４、５のすべてを満たす符号数をカウントする。
条件４．ハミング距離が指定したF以上である（F≦E）。
条件５．２つの符号語ＡとＢを連結して得られる２倍のDビットの２つのビット列（ＡＢとＢＡ）の任意のビットを最大２ビット反転させて得られるビット列において、連続する０または１がEビット以下である。ただし、２ビット反転する際は反転ビットは符号語Ａに１ビット、Ｂに１ビットかつ２つの反転ビット同士がFビット以上離れているものとする。
操作３．ＳＯの中で操作２によって得られたカウント数Ｎが２のC乗以上のものだけを抽出し、この集合をＳ１とする。
操作４．同様に操作２と操作３を集合の要素数が収束するまで繰り返す。最終的に得られた集合をＳｃとする。
操作５．Ｓｃを操作２によって得られたカウント数について昇順にソートし、順に配列Ｓに格納する。
操作６．配列の最初の要素Ｓ［０］から順に一つずつ符号語を取り出し、集合Ｓｔの要素として加える。ただし、Ｓｔは初め空集合であり、また加える符号語はＳｔの全符号語に対して、条件４と条件５すべてを満たす必要があり、条件を満たさない符号語はＳｔに加えない。
操作７．操作６によって得られたＳｔをＳｍａｘとし、その要素数をＭとする。
操作８．同様にＳ［１］から順に操作６を行い、Ｓｔの要素数がＭを上回れば、ＳｍａｘおよびＭを更新する。
操作９．操作８を配列Ｓの最後まで同様に繰り返す。
操作１０．ＳｍａｘがCBDB符号化の符号空間となる（ＭがＮ以上となっている）。  
【００２０】
このアルゴリズムにより、データ内にクロックを埋め込み（連続する０または１はEビット以下）、ＤＣバランシング（符号化後のDビット中の０と１が同数）、Dビット中２ビットの誤り検出、Dビット中１ビットの誤り訂正の各機能を同時に実現するように、CビットのデータをDビットのデータへ変換する符号を見つけることができる。
【００２１】
伝送路符号としてよく使用される８Ｂ１０ＢやＮＲＺＩ（Ｎｏｎ  Ｒｅｔｕｒｎ  ｔｏ  Ｚｅｒｏ  Ｉｎｖｅｒｔｅｄ）＋Ｂｉｔ  Ｓｔａｆｆｉｎｇ等の符号では、伝送路上のデータ１ビットが化けた場合でも、復号後に複数ビットのエラーとして検出される場合があるが、本発明によれば、復号時には伝送されてきたDビットをテーブル内から検索し、ハミング距離が１以内のものはエラーが訂正され正しく復号される。
【００２２】
以上、本発明の実施形態を説明したが、この実施形態は本発明の説明のための例示にすぎず、本発明の範囲をこの実施形態にのみ限定する趣旨ではない。例えば、エラー検出及びエラー訂正の強度の異なる符号化（何ビットエラー検出及び何ビットエラー訂正）は容易に実現できる。本発明は、その要旨を逸脱することなく、その他の様々な態様でも実施することができる。
【図１】
0005900850.tif 000004
【図２】
0005900850.tif 000005
【図３】
0005900850.tif 000006