TOP > 国内特許検索 > ディジタル通信の伝送路符号の送受信装置、ディジタル通信の伝送路符号の送受信方法、及びこの送受信装置又は送受信方法に用いる符号の生成方法 > 明細書

明細書 :ディジタル通信の伝送路符号の送受信装置、ディジタル通信の伝送路符号の送受信方法、及びこの送受信装置又は送受信方法に用いる符号の生成方法

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5900850号 (P5900850)
公開番号 特開2013-153394 (P2013-153394A)
登録日 平成28年3月18日(2016.3.18)
発行日 平成28年4月6日(2016.4.6)
公開日 平成25年8月8日(2013.8.8)
発明の名称または考案の名称 ディジタル通信の伝送路符号の送受信装置、ディジタル通信の伝送路符号の送受信方法、及びこの送受信装置又は送受信方法に用いる符号の生成方法
国際特許分類 H04L   1/00        (2006.01)
H03M   7/14        (2006.01)
FI H04L 1/00 B
H03M 7/14 B
請求項の数または発明の数 9
全頁数 11
出願番号 特願2012-014181 (P2012-014181)
出願日 平成24年1月26日(2012.1.26)
新規性喪失の例外の表示 特許法第30条第1項適用 一般社団法人情報処理学会が2011年(平成23年)11月21日に発行した、情報処理学会研究報告.[ハイパフォーマンスコンピューティング]2011-HPC-132(8)にて発表
審査請求日 平成26年11月27日(2014.11.27)
特許権者または実用新案権者 【識別番号】899000079
【氏名又は名称】学校法人慶應義塾
発明者または考案者 【氏名】山▲崎▼ 信行
個別代理人の代理人 【識別番号】100098545、【弁理士】、【氏名又は名称】阿部 伸一
【識別番号】100087745、【弁理士】、【氏名又は名称】清水 善廣
【識別番号】100106611、【弁理士】、【氏名又は名称】辻田 幸史
【識別番号】100189717、【弁理士】、【氏名又は名称】太田 貴章
【識別番号】100111006、【弁理士】、【氏名又は名称】藤江 和典
【識別番号】100116241、【弁理士】、【氏名又は名称】金子 一郎
審査官 【審査官】阿部 弘
参考文献・文献 特開2010-117605(JP,A)
特開2011-244212(JP,A)
国際公開第2010/146714(WO,A1)
特開2006-033329(JP,A)
国際公開第2002/073812(WO,A1)
調査した分野 H04L 1
H03M 7
H04L 25
特許請求の範囲 【請求項1】
ディジタル通信の伝送路符号の送受信装置であって、
シリアル通信のデータの中へのクロック埋め込み、DCバランシング、伝送中に発生するビット誤りの検出機能の内包、及び前記ビット誤りの訂正機能の内包、の全てを一度に行う符号化手段と、
前記符号化手段で符号化された符号語を送信する送信手段と、
受信した前記符号語について、前記ビット誤りの検出、及び前記ビット誤りの訂正を行う復号手段
を備え
前記符号化手段は、変換テーブルを用いて、CビットのデータをDビットのビット列の前記符号語に変換し、
前記変換テーブルは、前記各符号語のDビットのビット列において連続する0または1はEビット以下であり、前記各符号語のビット列において0と1とは同数であり、前記各符号語のビット列の任意の1ビットを反転させて得られるビット列において連続する0または1はEビット以下であり、前記各符号語のビット列同士においてハミング距離はF以上であり(F≦E)、
前記復号手段は、受信した前記符号語と前記変換テーブルの全ての前記各符号語のビット列とのハミング距離を算出し、算出した前記ハミング距離が最小となる符号語のビット列を前記変換テーブル内から選択し、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離が0の場合には伝送中のビット誤りは発生していないと判断して対応するCビットの前記データに復号し、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離がMの場合には伝送中にMビットの誤りが発生したと判断してビット誤りを訂正して対応するCビットの前記データに復号し(1≦M)、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離がN以上の場合には伝送中にNビット以上の誤りが発生したと判断してビット誤りを検出する(M<N)ことを特徴とするディジタル通信の伝送路符号の送受信装置
【請求項2】
ディジタル通信の伝送路符号の送受信装置であって、
シリアル通信のデータの中へのクロックの埋め込み、DCバランシング、伝送中に発生するビット誤りの検出機能の内包、及び前記ビット誤りの訂正機能の内包、の全てを一度に行う符号化手段と、
前記符号化手段で符号化された符号語を送信する送信手段と、
受信した前記符号語について、前記ビット誤りの検出、及び前記ビット誤りの訂正を行う復号手段と
を備え、
前記符号化手段は、変換テーブルを用いて、4ビットのデータを10ビットのビット列の前記符号語に変換し、
前記変換テーブルは、前記各符号語の10ビットのビット列において連続する0または1は5ビット以下であり、前記各符号語のビット列において0と1とは同数であり、前記各符号語のビット列の任意の1ビットを反転させて得られるビット列において連続する0または1は5ビット以下であり、前記各符号語のビット列同士においてハミング距離は4以上であり、
前記復号手段は、受信した前記符号語と前記変換テーブルの全ての前記各符号語のビット列とのハミング距離を算出し、算出した前記ハミング距離が最小となる符号語のビット列を前記変換テーブル内から選択し、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離が0の場合には伝送中のビット誤りは発生していないと判断して対応する4ビットの前記データに復号し、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離が1の場合には伝送中に1ビットの誤りが発生したと判断してビット誤りを訂正して対応する4ビットの前記データに復号し、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離が2以上の場合には伝送中に2ビット以上の誤りが発生したと判断してビット誤りを検出することを特徴とするディジタル通信の伝送路符号の送受信装置。
【請求項3】
前記変換テーブルは、表1で表されることを特徴とする請求項2に記載のディジタル通信の伝送路符号の送受信装置。
【表1】
JP0005900850B2_000002t.gif

【請求項4】
ディジタル通信の伝送路符号の送受信方法であって、
各符号語のDビットのビット列において連続する0または1はEビット以下であり、前記各符号語のビット列において0と1とは同数であり、前記各符号語のビット列の任意の1ビットを反転させて得られるビット列において連続する0または1はEビット以下であり、前記各符号語のビット列同士においてハミング距離はF以上である(F≦E)変換テーブルを生成するステップと、
前記変換テーブルを用いて、CビットのデータをDビットのビット列の符号語に変換するステップと、
変換した前記符号語を送信するステップと、
受信した前記符号語と前記変換テーブルの全ての前記各符号語のビット列とのハミング距離を算出するステップと、
算出した前記ハミング距離が最小となる符号語のビット列を前記変換テーブル内から選択するステップと、
受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離が0の場合には伝送中のビット誤りは発生していないと判断して対応するCビットの前記データに復号し、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離がMの場合には伝送中にMビットの誤りが発生したと判断してビット誤りを訂正して対応するCビットの前記データに復号し(1≦M)、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離がN以上の場合には伝送中にNビット以上の誤りが発生したと判断してビット誤りを検出する(M<N)ステップと
を備えることを特徴とするディジタル通信の伝送路符号の送受信方法。
【請求項5】
ディジタル通信の伝送路符号の送受信方法であって、
各符号語の10ビットのビット列において連続する0または1は5ビット以下であり、前記各符号語のビット列において0と1とは同数であり、前記各符号語のビット列の任意の1ビットを反転させて得られるビット列において連続する0または1は5ビット以下であり、前記各符号語のビット列同士においてハミング距離は4以上である変換テーブルを生成するステップと、
前記変換テーブルを用いて、4ビットのデータを10ビットのビット列の符号語に変換するステップと、
変換した前記符号語を送信するステップと、
受信した前記符号語と前記変換テーブルの全ての前記各符号語のビット列とのハミング距離を算出するステップと、
算出した前記ハミング距離が最小となる符号語のビット列を前記変換テーブル内から選択するステップと、
受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離が0の場合には伝送中のビット誤りは発生していないと判断して対応する4ビットの前記データに復号し、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離が1の場合には伝送中に1ビットの誤りが発生したと判断してビット誤りを訂正して対応する4ビットの前記データに復号し、受信した前記符号語と選択した前記符号語のビット列との前記ハミング距離が2以上の場合には伝送中に2ビット以上の誤りが発生したと判断してビット誤りを検出するステップと
を備えることを特徴とするディジタル通信の伝送路符号の送受信方法。
【請求項6】
前記変換テーブルは、表2で表されることを特徴とする請求項5に記載のディジタル通信の伝送路符号の送受信方法。
【表2】
JP0005900850B2_000003t.gif

【請求項7】
請求項2若しくは請求項に記載のディジタル通信の伝送路符号の送受信装置、又は請求項5若しくは請求項6に記載のディジタル通信の伝送路符号の送受信方法に用いる符号の生成方法であって、
それぞれの前記符号語を、
10ビット内で0と1とを同数とし、
前記符号語内の任意の1ビットを反転させて得られるビット列において、連続する0または1を5ビット以下とし、
2つの前記符号語を連結して得られる20ビットのビット列内の任意の1ビットを反転させて得られるビット列において、連続する0または1を5ビット以下とし、
ハミング距離を4以上とし、
2つの前記符号語を連結して得られる20ビットの前記ビット列内の任意の2ビットを反転させて得られるビット列において、連続する0または1を5ビット以下、ただし、2つの前記符号語を連結して得られる20ビットの前記ビット列内の一方の前記符号語内の任意の1ビットを反転させるとともに、他方の前記符号語内の任意の1ビットを反転させたときに、2つの反転ビット同士4ビット以上離れているもの
として生成することを特徴とする符号の生成方法。
【請求項8】
請求項1に記載のディジタル通信の伝送路符号の送受信装置、又は請求項4に記載のディジタル通信の伝送路符号の送受信方法に用いる符号の生成方法であって、
Cビットの送信データをDビットの符号語に変化する場合において、
それぞれの前記符号語を、
符号語Dビット内で0と1とを同数とし、
前記符号語内の任意の1ビットを反転させて得られるビット列において、連続する0または1を指定ビット(Eビット)以下とし、
2つの前記符号語を連結して得られる2倍のDビットのビット列内の任意の1ビットを反転させて得られるビット列において、連続する0または1をEビット以下とし、
ハミング距離を指定する数F以上とし(F≦E)、
2つの前記符号語を連結して得られる2倍のDビットの前記ビット列内の任意の2ビットを反転させて得られるビット列において、連続する0または1をEビット以下、ただし、2つの前記符号語を連結して得られる2倍のDビットの前記ビット列内の一方の前記符号語内の任意の1ビットを反転させるとともに、他方の前記符号語内の任意の1ビットを反転させたときに、2つの反転ビット同士Fビット以上離れているもの
として生成することを特徴とする符号の生成方法。
【請求項9】
請求項4から請求項6のいずれかに記載のディジタル通信の伝送路符号の送受信方法の全ステップをコンピュータに実行させることを特徴とするプログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、特に、シリアル通信においてデータにクロックを埋め込んで送信するエンベデッドクロック方式に関し、さらに、ディジタル通信の符号化に関わり、より詳細には、伝送路符号、誤り検出符号、誤り訂正符号に関するものである。
【背景技術】
【0002】
ディジタル通信では、伝送周波数の高速化に伴い、データにクロックを埋め込んで送信するエンベデッドクロック方式を用いた高速シリアル通信への要求が高まっている。エンベデッドクロック方式を用いた実用的な高速シリアル通信を実現するためには、送信信号のDCバランシング(0と1を同程度にする方法)を確保するための伝送路符号が必要となる。伝送路符号の実例として、「Byte Oriented DC Balanced(0,4)8B10B Partition Block Transmission Code」と題する、FranaszekおよびWidmerによる米国特許第4,486,739号に記載の8B10B伝送コードがPCI ExpressやInfiniBandなどの通信規格で採用されている。
【0003】
さらに、現代のディジタル通信においては、伝送路でのエラー検出やエラー訂正は必須の機能となっている。例えば、PCI Expressでは、CRCを用いてデータリンクレイヤでエラー検出を行っている。受信側でエラーが検出された場合、送信側にシーケンスナンバと共にNAK(Not Acknowledge)を返すことで、送信側が再送を行う。
【0004】
信頼性のない伝送路では、伝送中に発生するビット誤りを検出、および訂正する必要がある。誤り検出符号、および誤り訂正符号を用いることで、伝送中に発生するビット誤りを検出、および訂正が可能である。誤り検出符号、および誤り訂正符号の実例として、ハミング符号(非特許文献1)や、BCH符号(非特許文献2)などがある。
【先行技術文献】
【0005】

【非特許文献1】R.W.Hamming;Error Detecting and Error Correcting Codes, Bell System Technical Journal, Vol.29, pp.147-160(1950)
【非特許文献2】R.C.Bose and D.K.Ray-Chaudhuri;On A Class of Error Correcting Binary Group Codes, Information and Control 3, Vol.1, pp.68-79(1960)
【発明の開示】
【発明が解決しようとする課題】
【0006】
エンベデッドクロック方式で用いられる伝送路符号では、DCバランシングを確保するために伝送データをより長いビット列に符号化するという特性上、伝送中に発生するビット誤りが、復号後により大きな誤りとなる場合がある。(以下、元データを符号化したデータ(ビット列)を符号語と呼称する。)例えば伝送中にビット誤りが発生し、正しい符号語からハミング距離が1離れたとすると、誤った符号語を復号した結果、復号されたデータは正しいデータからハミング距離が1以上離れる可能性がある。この結果、復号後の誤り検出、および訂正のコストが非常に高くなる。8B10B伝送コードのようなエンべデッドクロック方式でエラー訂正を同時に行いたい場合には、ビット単位でのエラー訂正は用いることが困難であり、リードソロモン符号のようなブロックエラー訂正符号をパケット単位(大きなブロック単位)で後段に行う必要がある。この場合には、パケットをすべて受信しきらないとエラー訂正を行うことができず、レイテンシが長くなり、リアルタイム通信等には不向きとなる。
ここで、近年、ヒューマノイドロボット等の複雑なリアルタイムシステムの出現により、単一プロセッサで行う処理の限界や、システムの耐故障性等を向上するために、プロセッサを複数用いた分散リアルタイムシステムへの要求が高まっている。
分散リアルタイムシステムでは、ノード内の処理においてリアルタイム性を満たすだけでなく、ノード間の通信においてもリアルタイム性を保証しなければならない。このような背景から、分散リアルタイムシステムのための通信機構としてレスポンシブリンク(Responsive Link)が国内外で標準化されている。具体的には、レスポンシブリンクは、国内ではIPSJ-TS 0006として、国際的にはISO/IEC 24740として標準化されている。
【0007】
従って、本発明の目的は、エンベデッドクロック方式の伝送路符号に、DCバランシング、誤り検出および誤り訂正機能を内包することで、誤り検出および誤り訂正を同時に実現することにある。具体的には、従来手法では不可能であった、データにクロックを埋め込んで通信、DCバランシング、エラー検出機能、エラー訂正機能、を一つの符号で同時に行う。エラー検出及びエラー訂正機能付きのエンべデッドクロック方式の伝送路符号化を実現することで、信頼性が高くレイテンシも短いシリアルデータ通信を実現する。
【課題を解決するための手段】
【0008】
本発明によるディジタル通信の伝送路符号の変換方法は、ディジタル通信の伝送路符号の変換方法であって、シリアル通信のデータの中にクロックを埋め込み、前記クロックの埋め込みの際にDCバランシングを行い、前記データと前記クロックの転送を同じ配線で行うことが可能な符号化手段と、前記符号化手段で符号化された符号語について、伝送中に発生するビット誤りの検出を行う誤り検出手段と、前記誤り検出手段で検出された前記ビット誤りの訂正を行う誤り訂正手段とを備えたことを特徴とする。
また、本発明によるディジタル通信の伝送路符号の一例(以下、4B10B符号と称す)を以下に示す。前記符号化手段では、変換テーブルを用いて4ビットの送信データを10ビットの前記符号語に変換し、DCバランシングを実現しつつ、データ内にクロックを埋め込む。
また、本発明によるディジタル通信の伝送路符号の一つである4B10B符号では、それぞれの前記符号語は、連続する0または1が5ビット以下であることを特徴とし、伝送中に発生する10ビット中1ビット以内のビット誤りが発生してもエンベデッドクロックを維持できる。
また、本発明によるディジタル通信の伝送路符号の一つである4B10B符号では、それぞれの前記符号語は、前記符号化した各ビット列同士のハミング距離が4以上であり、前記誤り検出手段では、10ビット中2ビット以内のビット誤りの検出を行うことを特徴とする。
また、本発明によるディジタル通信の伝送路符号の一つである4B10B符号では、前記誤り訂正手段では、10ビット中1ビットのビット誤りの訂正を行うことを特徴とする。
また、本発明によるディジタル通信の伝送路符号の一つである4B10B符号化を行う符号の生成方法は、それぞれの前記符号語を、10ビット内で0と1とを同数とし、前記符号語内の任意の1ビットを反転させて得られるビット列において、連続する0または1を5ビット以下とし、2つの前記符号語を連結して得られる20ビットのビット列内の任意の1ビットを反転させて得られるビット列において、連続する0または1を5ビット以下とし、ハミング距離を4以上とし、2つの前記符号語を連結して得られる20ビットの前記ビット列内の任意の2ビットを反転させて得られるビット列において、連続する0または1を5ビット以下とし、2つの前記符号語を連結して得られる20ビットの前記ビット列内の一方の前記符号語内の任意の1ビットを反転させるとともに他方の前記符号語内の任意の1ビットを反転させたときに、2つの反転ビット同士を4ビット以上として生成することを特徴とする。
また、本発明によるディジタル通信の伝送路符号の変換方法を行う符号の生成方法は、それぞれの前記符号語を、10ビット内で0と1とを同数とし、前記符号語内の任意の1ビットを反転させて得られるビット列において、連続する0または1を5ビット以下とし、
2つの前記符号語を連結して得られる20ビットのビット列内の任意の1ビットを反転させて得られるビット列において、連続する0または1を5ビット以下とし、ハミング距離を4以上とし、2つの前記符号語を連結して得られる20ビットの前記ビット列内の任意の2ビットを反転させて得られるビット列において、連続する0または1を5ビット以下とし、2つの前記符号語を連結して得られる20ビットの前記ビット列内の一方の前記符号語内の任意の1ビットを反転させるとともに他方の前記符号語内の任意の1ビットを反転させたときに、2つの反転ビット同士を4ビット以上として生成することを特徴とする。
【発明の効果】
【0009】
本発明によれば、ラインコード自体にエラー検出機能とエラー訂正機能の両方を持たせて信頼性の高い通信を実現することができる。
【図面の簡単な説明】
【0010】
【図1】本発明による4B10B符号を示す変換テーブル
【図2】本発明によるビット誤りによるハミング距離と、誤り検出、および誤り訂正の概要を示す図
【図3】本発明によるデコードのフローチャート
【発明を実施するための形態】
【0011】
本発明に従った符号化(4B10B符号化)を、図1に示す変換テーブルを用いて例示する。図1では、4ビットの元データを10ビットのデータ(符号語)へ変換することで、元データ内にクロックを埋め込み、DCバランシング(0と1の割合をまったく同じにする)を実現し、10ビットのデータ中の2ビットの誤りを検出し、10ビットのデータ中の1ビットの誤り訂正をするという各機能を同時に実現する。

【0012】
図1に示す変換テーブルによれば、符号化した10ビットの各ビット列において連続する0または1は必ず5ビット以下になるようにしつつ、クロックを埋め込んでいる。さらには、この符号語内で任意の1ビットが反転しても連続する0または1は5ビット以下になるようにしている。例えば、符号語が「1100110010」であったとした場合、符号語内の一つの任意の「1」に誤りが生じて「0」に反転した場合であっても、連続するビットは5ビット以下となる。
同様に、任意の符号化した10ビットと別の符号化した10ビットの符号語間においても連続する0または1は必ず5ビット以下になるようにしている。この結合部分においても任意の1ビットが反転しても連続する0または1は5ビット以下になるようにしている。したがって、各符号語で誤りがある場合は誤りビット同士が4ビット以上離れているときに不連続性を保証する。例えば、2つの符号語が、「1100110010」と「1001110001」であった場合、「1100110010」が「1100110000」となり、「1001110001」が「1000110001」となっても、2つの誤りビットが4ビット以上離れていれば、連続するビットは5ビット以下となる。

【0013】
図1に示す変換テーブルによれば、符号化した10ビットの符号語内の0と1の数を必ず同数になるようにし、DCバランシングを実現する。

【0014】
図1に示す変換テーブルによれば、符号化した10ビットの各ビット列同士のハミング距離は4以上離れており、伝送中に発生する10ビット中1ビットの誤りは、正しいビット列が一意に決まるため、誤りの訂正が可能である。ビット誤りによるハミング距離と、誤り検出、および誤り訂正の概要を図2に示す。

【0015】
本発明に従えば、符号化を行う符号器は図1に示した変換テーブルに基づき、4ビットのデータから10ビットの符号語を生成する。復号化を行う復号器は、入力された10ビットの符号語を図1に示した変換テーブルの全てのビット列とのハミング距離を求め、変換テーブル内でハミング距離が最も小さいものが選択され、復号される。最も小さいハミング距離が0だった場合、伝送中のビット誤りは存在せず、正しく復号化される。ハミング距離が1だった場合、伝送中に1ビットの誤りが発生したことになり、誤りは訂正されて正しく復号化される。ハミング距離が2以上だった場合、伝送中に2ビット以上の誤りが発生したことになり、誤りは検出できるが、訂正はできない。10ビット中2ビットまでの誤りを検出することができる。図3に復号のフローを示す。

【0016】
図1に示す4B10B符号化変換テーブルを生成するアルゴリズムを以下に示す。
操作1.10ビットの符号語から以下の条件1、2、3をすべて満たすものだけを抽出し、この集合をSOとする。
条件1.10ビット内で0と1が同数である。
条件2.符号語内の任意のビットを1ビット反転させて得られるビット列において、連続する0または1が5ビット以下である。
条件3.符号自身を2つ連結して得られる20ビットのビット列内の任意のビットを1ビット反転させて得られるビット列において、連続する0または1が5ビット以下である。
操作2.SOの各符号語について、SO中の他の符号語すべてに対して、それぞれ、以下の条件4、5のすべてを満たす符号数をカウントする。
条件4.ハミング距離が4以上である。
条件5.2つの符号語AとBを連結して得られる20ビットの2つのビット列(ABとBA)の任意のビットを最大2ビット反転させて得られるビット列において、連続する0または1が5ビット以下である。ただし、2ビット反転する際は反転ビットは符号語Aに1ビット、Bに1ビットかつ2つの反転ビット同士が4ビット以上離れているものとする。
操作3.SOの中で操作2によって得られたカウント数Nが16以上のものだけを抽出し、この集合をS1とする。
操作4.同様に操作2と操作3を集合の要素数が収束するまで繰り返す。最終的に得られた集合をScとする。
操作5.Scを操作2によって得られたカウント数について昇順にソートし、順に配列Sに格納する。
操作6.配列の最初の要素S[0]から順に一つずつ符号語を取り出し、集合Stの要素として加える。ただし、Stは初め空集合であり、また加える符号語はStの全符号語に対して、条件4と条件5すべてを満たす必要があり、条件を満たさない符号語はStに加えない。
操作7.操作6によって得られたStをSmaxとし、その要素数をMとする。
操作8.同様にS[1]から順に操作6を行い、Stの要素数がMを上回れば、SmaxおよびMを更新する。
操作9.操作8を配列Sの最後まで同様に繰り返す。
操作10.Smaxが4B10B符号化の符号空間となる(MがN(=16)以上となっている)。

【0017】
このアルゴリズムにより、データ内にクロックを埋め込み(連続する0または1は5ビット以下)、DCバランシング(符号化後の10ビット中の0と1が同数)、10ビット中2ビットの誤り検出、10ビット中1ビットの誤り訂正の各機能を同時に実現するように、4ビットのデータを10ビットのデータ(符号語)へ変換する符号を見つけることができる。

【0018】
伝送路符号としてよく使用される8B10BやNRZI(Non Return to Zero Inverted)+Bit Staffing等の符号では、伝送路上のデータ1ビットが化けた場合でも、復号後に複数ビットのエラーとして検出される場合があるが、本発明によれば、復号時には伝送されてきた10ビットをテーブル内から検索し、ハミング距離が1以内のものはエラーが訂正され正しく復号される。

【0019】
より一般的にCビットの元データをDビットの符号語に変換する変換テーブルを生成するアルゴリズムを以下に示す(C<D)。
操作1.Dビットの符号語から以下の条件1、2、3をすべて満たすものだけを抽出し、この集合をSOとする。
条件1.Dビット内で0と1が同数である。
条件2.符号語内の任意のビットを1ビット反転させて得られるビット列において、連続する0または1が指定ビット(Eビット)以下である。
条件3.符号自身を2つ連結して得られる2倍のDビットのビット列内の任意のビットを1ビット反転させて得られるビット列において、連続する0または1がEビット以下である。
操作2.SOの各符号語について、SO中の他の符号語すべてに対して、それぞれ、以下の条件4、5のすべてを満たす符号数をカウントする。
条件4.ハミング距離が指定したF以上である(F≦E)。
条件5.2つの符号語AとBを連結して得られる2倍のDビットの2つのビット列(ABとBA)の任意のビットを最大2ビット反転させて得られるビット列において、連続する0または1がEビット以下である。ただし、2ビット反転する際は反転ビットは符号語Aに1ビット、Bに1ビットかつ2つの反転ビット同士がFビット以上離れているものとする。
操作3.SOの中で操作2によって得られたカウント数Nが2のC乗以上のものだけを抽出し、この集合をS1とする。
操作4.同様に操作2と操作3を集合の要素数が収束するまで繰り返す。最終的に得られた集合をScとする。
操作5.Scを操作2によって得られたカウント数について昇順にソートし、順に配列Sに格納する。
操作6.配列の最初の要素S[0]から順に一つずつ符号語を取り出し、集合Stの要素として加える。ただし、Stは初め空集合であり、また加える符号語はStの全符号語に対して、条件4と条件5すべてを満たす必要があり、条件を満たさない符号語はStに加えない。
操作7.操作6によって得られたStをSmaxとし、その要素数をMとする。
操作8.同様にS[1]から順に操作6を行い、Stの要素数がMを上回れば、SmaxおよびMを更新する。
操作9.操作8を配列Sの最後まで同様に繰り返す。
操作10.SmaxがCBDB符号化の符号空間となる(MがN以上となっている)。

【0020】
このアルゴリズムにより、データ内にクロックを埋め込み(連続する0または1はEビット以下)、DCバランシング(符号化後のDビット中の0と1が同数)、Dビット中2ビットの誤り検出、Dビット中1ビットの誤り訂正の各機能を同時に実現するように、CビットのデータをDビットのデータへ変換する符号を見つけることができる。

【0021】
伝送路符号としてよく使用される8B10BやNRZI(Non Return to Zero Inverted)+Bit Staffing等の符号では、伝送路上のデータ1ビットが化けた場合でも、復号後に複数ビットのエラーとして検出される場合があるが、本発明によれば、復号時には伝送されてきたDビットをテーブル内から検索し、ハミング距離が1以内のものはエラーが訂正され正しく復号される。

【0022】
以上、本発明の実施形態を説明したが、この実施形態は本発明の説明のための例示にすぎず、本発明の範囲をこの実施形態にのみ限定する趣旨ではない。例えば、エラー検出及びエラー訂正の強度の異なる符号化(何ビットエラー検出及び何ビットエラー訂正)は容易に実現できる。本発明は、その要旨を逸脱することなく、その他の様々な態様でも実施することができる。
図面
【図1】
0
【図2】
1
【図3】
2