(57)【要約】【課題】本発明の実施形態は、符号化／復号器（コーデック）を使用して禁止パターンなし（ＦＰＦ）コードワードを生成する方法を説明する。【解決手段】まず、本方法は、データワードをフィボナッチ記数法空間にマッピングすることによって、データワードを符号化してＦＰＦコードワードを生成する。さらに、ＦＰＦコードワードはバスの隣接するラインを介して送信され、バスから受信されると復号されてデータワードが復元され、バス上のすべてのクロストークがなくなる。【選択図】図１
2009232461.tif 000002
【特許請求の範囲】
【請求項１】
バス内のクロストークを低減する方法であって、
フィボナッチ禁止パターンなし（ＦＰＦ）コードワードを生成するために、フィボナッチ数列を使用してデータワードを符号化することと、
前記ＦＰＦコードワードを、バスの複数の隣接するラインを介して送信することと、
前記複数のラインのすべてにおけるクロストークをなくしながら、前記データワードを復元するために、前記バスから受信される前記ＦＰＦコードワードを復号することと
を含む方法。
【請求項２】
前記データワードを二進記数法で、また前記ＦＰＦコードワードをフィボナッチ記数法で提示することをさらに含む請求項１に記載の方法。
【請求項３】
前記符号化は、ｍビット長の前記ＦＰＦコードワードを生成するｍ−１個のステージからなり、各ステージｋの符号化は、
あるステージｋに対する剰余入力ｒｋ＋１を、前記フィボナッチ数列の対応する２つの連続する要素ｆｋ＋１及びｆｋと比較することと、
ｒｋ＋１≧ｆｋ＋１の場合、前記ステージｋの出力ｄｋに値１を割り当てることと、
ｒｋ＋１＜ｆｋの場合、前記ステージｋの前記出力ｄｋに値０を割り当てることと、
そうでない場合、前記出力ｄｋに、先行するステージｋ＋１の出力ｄｋ＋１の値を割り当てることと
を含む請求項１に記載の方法。
【請求項４】
前記各ステージｋの符号化は、前記ステージｋの前記符号化の剰余ｒｋを、後続のステージｋ−１に対する入力として送信することをさらに含む請求項３に記載の方法。
【請求項５】
最上位ビットステージｋの前記出力ｄｋは、０である請求項３に記載の方法。
【請求項６】
最上位ビットステージｋの前記出力ｄｋは、１である請求項３に記載の方法。
【請求項７】
最上位ビットステージｋの前記出力ｄｋは、前記データワードの最上位ビットに等しい請求項３に記載の方法。
【請求項８】
重複するＦＰＦフィボナッチベクトルが存在する領域における値の冗長性を除去するために、前記ＦＰＦコードワードの値をｆｍ＋１だけシフトすることをさらに含む請求項１に記載の方法。
【請求項９】
前記バスの前記複数のラインを、ラインのグループのセットに分割することと、
前記セット内のラインの各グループに、独立して前記符号化することを適用することと
をさらに含む請求項１に記載の方法。
【請求項１０】
データワードをコードワードに符号化する方法であって、
データワードを、フィボナッチ記数法によって表されるコードワードのセットに変換することと、
前記コードワードのセットからフィボナッチ禁止パターンなし（ＦＰＦ）コードワードを選択することと、
前記データワードを符号化ＦＰＦコードワードとして表現することと、
前記ＦＰＦコードワードを、バスの複数の隣接するラインを介して、該複数のラインのすべてにおけるクロストークをなくしながら送信することと
を含む方法。
【請求項１１】
前記変換すること及び前記選択することは、ｍビット長の前記コードワードを生成するｍ−１個のステージからなり、各ステージｋの符号化は、
前記ステージｋに対する入力ｒｋ＋１を、前記フィボナッチ数列の対応する２つの連続する要素ｆｋ＋１及びｆｋと比較することと、
ｒｋ＋１≧ｆｋ＋１の場合、前記ステージｋの出力ｄｋに値１を割り当てることと、
ｒｋ＋１＜ｆｋの場合、前記ステージｋの前記出力ｄｋに値０を割り当てることと、
そうでない場合、前記出力ｄｋに、先行するステージｋ＋１の出力ｄｋ＋１の値を割り当てることと
を含む請求項１０に記載の方法。
【請求項１２】
前記各ステージｋの符号化は、前記ステージｋの前記符号化の剰余ｒｋを、後続のステージｋ−１に対する入力として送信することをさらに含む請求項１１に記載の方法。
【請求項１３】
最上位ビットステージｋの前記出力ｄｋは、前記データワードの最上位ビットに等しい請求項１１に記載の方法。
【請求項１４】
グレー領域における値の冗長性を除去するために、前記選択されたコードワードの値をｆｍ＋１だけシフトすることをさらに含む請求項１０に記載の方法。
【請求項１５】
バス内のクロストークを、該バスを介してデータワードを送信しながら低減する装置であって、
データワードを符号化するように構成され、それによって、該データワードは、フィボナッチ禁止パターンなし（ＦＰＦ）コードワードが、前記バスの複数の隣接するラインを介して、該複数のラインのすべてにおけるクロストークをなくしながら送信されるときに、該コードワードとして表現される符号化器を備える装置。
【請求項１６】
前記コードワードを復号して前記データワードを復元するように構成される復号器と、
前記コードワードを、前記符号化器から前記復号器へ送信する手段と
をさらに備える請求項１５に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはバス上の信号伝達に関し、より詳細には、符号化器及び復号器（コーデック）、並びに、禁止パターンなしコードを使用して符号化及び復号するシステム及び方法に関する。
【背景技術】
【０００２】
バス内のクロストーク
長く幅の広い大域バスを有する回路では、相互接続遅延が信号遅延を占めることが多い。たとえば、超大規模集積（ＶＬＳＩ）プロセスによるディープサブミクロン（ＤＳＭ）チップでは、バスベースの相互接続のパフォーマンスがシステム全体のパフォーマンスに対するボトルネックになっている。
【０００３】
容量性クロストーク、すなわち、バス内の隣接するワイヤ間の結合容量に起因するクロストークは、さらなるエネルギー消費及び信号遅延を誘発する。したがって、クロストークは最大バス速度を制限すると共に、総電力消費を上昇させる。
【０００４】
クロストーク分類
図２は、クロストークを受ける一例のオンチップバスを示している。ＣＬは、受信機ゲート容量と、ワイヤ−基板寄生容量とを含む、ｊ番目のビットのドライバによって見込まれる負荷容量である。ＣＩは、図２におけるバスのｊ番目のラインと隣接する信号ライン、すなわち（ｊ−１）番目のライン及び（ｊ＋１）番目のラインとの間のワイヤ間結合容量である。
【０００５】
バス内のｊ番目のラインの遅延τｊは以下の通りである。
τｊ＝ａｂｓ（ｋ・ＣＬ・ΔＶｊ＋ｋ・ＣＩ・ΔＶｊ−１＋ｋ・ＣＩ・ΔＶｊ＋１）                                                                          （１）
ここで、ｋはドライバ強度及び線路抵抗によって求められる定数であり、ΔＶｊはｊ番目のワイヤにおける電圧変化であり、ΔＶｊ，ｋ＝ΔＶｊ−ΔＶｋはｊ番目のラインとｋ番目のラインとの間の相対電圧変化である。
【０００６】
通常、オンチップバスは全振幅二値バスであり、したがって２つの出力電圧レベルはＶｄｄ及び０Ｖであり、したがって以下のようになる。
１．ΔＶｊ∈｛０，±Ｖｄｄ｝かつΔＶｊ，ｋ∈｛０，±Ｖｄｄ，±２Ｖｄｄ｝
【０００７】
式（１）は以下のように書くことができる。
τｊ＝ｋ・ＣＬ・Ｖｄｄ・ａｂｓ（δｊ＋λ・δｊ，ｊ−１＋λ・δｊ，ｊ＋１）                                                                            （２）
ここで、λ＝ＣＩ／ＣＬ及びδｊ∈｛０，１｝はｊ番目のラインにおける正規化された電圧変化であり、δｊ，ｊ＋１∈｛０，±１，±２｝は、ｊ番目のラインにおける、（ｊ＋１）番目のライン、又は（ｊ−１）番目のラインに対する、正規化された相対電圧変化である。δｊ項は真性遅延に対応し、δｊ，ｊ±１項はクロストークによって誘発される遅延に対応する。λ≫１であるため、δｊは遅延に対してごくわずかにしか寄与しない。
【０００８】
Ｃｅｆｆ，ｊは、ｊ番目のラインのドライバの実効全容量として定義される。
Ｃｅｆｆ，ｊ＝ＣＬ・ａｂｓ（δｊ＋λ・δｊ，ｊ−１＋λ・δｊ，ｊ＋１）                                                                                （３）
【０００９】
式（２）は、以下のように書き換えることができる。
τｊ＝ｋ・Ｖｄｄ・Ｃｅｆｆ．ｊ                                        （４）
【００１０】
式（３）は、ｍｉｎ（Ｃｅｆｆ，ｊ）＝ＣＬであり、かつｍａｘ（Ｃｅｆｆ，ｊ）＝（１＋４λ）ＣＬであることを実証している。
【００１１】
クロストークパターンは、表Ｉの第１列に示されているような０Ｃ、１Ｃ、２Ｃ、３Ｃ、及び４Ｃのパターンとしてそれぞれ分類される。中央列はＣｅｆｆであり、表Ｉ内の最後の列は、バスの３つの隣接するビットｂｊ＋１、ｂｊ、ｂｊ−１における一例の遷移パターンを記載している。
【００１２】
【表１】
2009232461.tif 000003
【００１３】
データバスの速度はバスｊのすべてのライン又はビットにわたるｍａｘ｛Ｃｅｆｆ，ｊ｝によって求められる。バスのすべてのライン上の４Ｃクラスのクロストークをなくすことによって、バスの最大速度は約３３％増加する。３Ｃクラス及び４Ｃクラスの遷移パターンをなくすことによってバスの最大速度は約１００％増加する。
【００１４】
クロストークを低減する従来の方法
クロストークを低減する多数の従来の方法が存在する。
【００１５】
受動的遮蔽
クロストークを低減する受動的遮蔽方法は、隣接する能動データワイヤ間に受動シールド、たとえば接地ワイヤを挿入する。この方法は、クロストークによって誘発されるバス遅延をほぼ５０％低減することができ、したがってバス速度をほぼ１００％ブーストすることができる。しかしながら、受動的遮蔽は回路のサイズを増大させる。
【００１６】
能動的遮蔽
能動的遮蔽方法は、データワイヤ間に遮蔽ワイヤを挿入する。遮蔽ワイヤは、遮蔽されるデータワイヤと同じ方向に遷移する。能動的遮蔽の単純な事例では、各データビットが３本のワイヤ上で送信される。受信機側では、中央のワイヤのみがデータの復元に使用される。他の２本のワイヤは遮蔽ワイヤとして使用される。能動的遮蔽はより積極的であり、バス遅延を最大７５％低減するが、回路のサイズも増大させる。
【００１７】
物理的配置
ワイヤ幅、深度、及びワイヤ間の間隔を含むバスの寸法を調整することによってクロストークを低減することもできる。このような方法は、大きなオーバヘッドを受け、プロセス変動の影響を受けやすい。
【００１８】
意図的なデータスキューイング
意図的なデータスキューイングは、バスにおけるデータビットの遷移に時間オフセットを意図的に導入することによってクロストークを低減する。このような方法は、非常に時間のかかる物理配置操作を必要とし、プロセス変動の影響も受けやすい。
【００１９】
クロストーク回避コード
特別な種類のコード又はコードワードがバス上で送信されると、特定の種類のクロストークがなくなる。これらのコードは一般にクロストーク回避コード（ＣＡＣ）と呼ばれる。
【００２０】
バス符号化方法は、元のデータワードをＣＡＣコードワードに符号化し、次いで、それらをバス上で送信する。これらの方法は、より低い面積オーバヘッドで、受動的遮蔽方法と同程度のバス遅延低減を達成することができる。
【００２１】
ＣＡＣはメモリなしとすることもできるし、又はメモリベースとすることもできる。メモリベースのＣＡＣは、以前に送信されたコードワード、及び現在送信されているコードワードに基づいてコードワードを使用する。受信機側では、コードワード復元は現在のコードワード及び以前のコードワードに基づく。メモリなしのＣＡＣは、固定コードブックを使用してコードワードを生成し、入力データのみに基づいて送信する。受信機は現在のコードワードを唯一の入力として使用して入力データを復元する。
【００２２】
コーデックは、デジタルデータストリーム又は信号に対して符号化及び復号を実施することが可能な装置又はプログラムである。メモリベースのＣＡＣに対する面積オーバヘッドは、メモリなしのＣＡＣと比較してより低いものであり得る。しかしながら、メモリベースのＣＡＣのためのコーデックは、メモリなしのＣＡＣよりもはるかに複雑である。
【００２３】
禁止パターンなしコード
禁止パターンなしコードはメモリなしのコードであり、バス相互接続におけるクロストーク回避に使用することができる。それによって、より少ない面積オーバヘッドで、受動的遮蔽方法と同量の遅延低減が可能となる。従来のコーデックは、バス分割及びブルートフォース論理最適化に基づき、それによって、幅の広いバスが多数の小さなグループ（レーン）に分割され、各グループに独立してＣＡＣ符号化が適用される。これらの方法は、グループ境界にわたるクロストークに対処する。
【発明の概要】
【発明が解決しようとする課題】
【００２４】
これらのすべての方法において、必須の最小数のワイヤよりも多くのワイヤがバス内に必要とされ、したがって全面積オーバヘッドは論理的な下界よりも高くなる。これによって、最適でない面積オーバヘッド、及び全電力消費がもたらされる。効率的に実施することができると共に、高データ転送速度で動作することができるコーデックを有することが望まれている。
【課題を解決するための手段】
【００２５】
本発明の実施の形態は、禁止パターンなし（ＦＰＦ）コードを使用してのバス上のデータの符号化を提供する。この設計は、フィボナッチ記数法（ＦＮＳ）に基づく。本発明の実施の形態は、小さなバスを有するコーデックの単純な拡張として、大きなバスを有するコーデックを構築することを可能にする。
【００２６】
本発明の実施の形態によるバスを有するコーデックは、最適又は近最適な面積オーバヘッドパフォーマンス、並びに、回路複雑性及び速度の両方における高い効率を提供する。コーデックは、効率的で高速な実施も可能にし、したがってＦＲＦコードがオンチップバスクロストーク回避、バス速度向上、及びエネルギー消費低減に使用されることを可能にする。
【発明の効果】
【００２７】
本発明の実施の形態は、禁止パターンなしクロストーク回避コード（ＦＰＦ−ＣＡＣ）のためのコーデック設計を提供する。このマッピング方式はフィボナッチ記数法における数の表現に基づく。
【００２８】
本発明の一実施の形態は、近最適な面積オーバヘッドパフォーマンスを提供する。本発明の別の実施の形態は、論理的な下界に達する改善された面積オーバヘッドを提供する。
【００２９】
説明されるシステム及び方法は、任意のバスサイズのためのコーデックが体系的な様式で設計されることを可能にする。このような決定論的で体系的なマッピングによって、より幅の広いバスを有するコーデックの構築は、より小さいバスのコーデックの単純な拡張となる。本発明の符号化器はモジュール構造を有し、それによってモジュールを再使用することが可能となる。
【００３０】
コーデックの複雑性を低減すると共に遅延パフォーマンスを改善する本発明の近最適コーデックに対する変更を説明する。
【００３１】
本発明の実施形態はコーデックバスに関して説明されるが、本発明を任意の高速オンチップバスに使用することができることは理解されたい。
【図面の簡単な説明】
【００３２】
【図１】本発明の実施形態による、バス上のクロストークを低減する方法及びシステムのブロック図である。
【図２】クロストークを伴っているオンチップバスの概略図である。
【図３】本発明の実施形態による、二値ベクトルをＦＰＦフィボナッチベクトルに符号化する近最適ＦＰＦ−ＣＡＣ符号化方法の擬似コードである。
【図４】（Ａ）図３の擬似コードに基づく符号化器の実施態様のブロック図、（Ｂ）本発明の実施形態による、近最適ＦＰＦコード復号動作のための復号器の実施態様のブロック図である。
【図５】本発明の実施形態による、符号化器動作の１つのステージの一実施態様のブロック図である。
【図６】本発明の実施形態による、単純化されたＭＳＢステージを有する変更されたコーデックのブロック図である。
【図７】本発明の実施形態による、２つのグループに分割された入力バスのためのコーデックのブロック図である。
【発明を実施するための形態】
【００３３】
システム概説
図１は、オンチップバス内のクロストークを低減する方法及びシステム１００を示している。本発明の好ましい実施形態のバスはコーデックに関して説明される。しかしながら、本発明を任意の高速バスと共に使用することができることは理解されたい。コーデックは、一連のデータワード１０のうちの現在のデータワード２０を、フィボナッチベースの、禁止パターンなしクロストーク回避コード（ＦＰＦ−ＣＡＣ）のコードワード４０に符号化する（３０）。コードワードはバス５０を介して送信される。コードワード４０は復号され（６０）、データワード２０が復元される。データワード２０は方法及びシステム１００の入力であると共に出力である。後述するように、データワード２０を表す、少なくとも１つの、ｍビットフィボナッチ「禁止パターン」なしコードワード４０が存在する。
【００３４】
禁止パターンなし（ＦＰＦ）コード
禁止パターンは、２つの３ビット二値パターン、すなわち「１０１」及び「０１０」として定義される。コード内の連続する３ビットのいずれもが禁止パターンを有しない場合、ｍビットコードは禁止パターンなしである。このようなコードを禁止パターンなし（ＦＰＦ）コードと定義する。一例として、０１１０００は６ビットＦＰＦコードであり、０１００００及び０１１１０１はＦＰＦコードではない。
【００３５】
ＦＰＦコードワードのみがバス上で送信される場合、任意の遷移時点における任意のワイヤ上の最大クロストークは、約半分低減される。したがって、データワードをＦＰＦコードワードに符号化することによって、本発明は、バスを約１００％加速することができる。この種類のコードを、本明細書では禁止パターンなしクロストーク回避コード（ＦＰＦ−ＣＡＣ）と呼ぶ。参照により本明細書に援用される、C. Duan他著「Analysis and Avoidance of Crosstalk in On-chip Bus」（Hot-Interconnects, 2001, pp 133-138）を参照されたい。
【００３６】
フィボナッチ数列
ｍビットＦＰＦ−ＣＡＣコードの最大濃度Ｔｇ（ｍ）は以下の通りである。
Ｔｇ（ｍ）＝２ｆｍ＋１                                                （５）
ここで、ｆｍはフィボナッチ数列のｍ番目の要素である。フィボナッチ数列ｆｍは以下のように定義される。
【００３７】
【数１】
2009232461.tif 000004
【００３８】
フィボナッチ数列の別の恒等式は以下の通りである。
【００３９】
【数２】
2009232461.tif 000005
【００４０】
ｎビット二値バスをＦＰＦ−ＣＡＣコードに符号化するために、必要とされる最小ビット数ｍｏｐｔは、式（８）を満たす最小の整数ｍである。符号化されたバスに必要な追加の面積と、符号化されていないバスの面積との間の比として定義される、面積オーバヘッドＯＨ（ｎ）の下界を計算する。
【００４１】
【数３】
2009232461.tif 000006
【００４２】
黄金比、すなわち、下式は、フィボナッチ数列の２つの連続する要素の漸近的な比である。
【００４３】
【数４】
2009232461.tif 000007
【００４４】
したがって、下式である。
【００４５】
【数５】
2009232461.tif 000008
【００４６】
ここで、ｃは定数である。したがって、幅の広いバスに関して、オーバヘッドの下界は以下の通りである。
ＯＨ（ｎ）≧（１／ｌｏｇ２φ）−１≒４４％                          （１０）
【００４７】
フィボナッチベースの記数法
記数法とは「数が一貫した様式の数表示で表される枠組み」である。デジタル回路において一般に使用されている記数法は二進記数法であり、これは２の累乗を底として使用する。二進記数法は式（１１）によって定義される。二値記数法は完全かつ一義的であり、これは各数ｖがこの二値記数法において唯一の表現であることを意味する。
【００４８】
【数６】
2009232461.tif 000009
【００４９】
ここで、ｋはビット位置であり、ｂｋはｋ番目のビットの二進値である。
【００５０】
フィボナッチベースの記数法Ｎ（Ｆｍ，｛０，１｝）とは、フィボナッチ数列を底として使用する記数法である。式（１２）において定義されるように、数ｖはいくつかのフィボナッチ数の総和として表され、いかなるフィボナッチ数も総和において２回以上現れない。
【００５１】
【数７】
2009232461.tif 000010
【００５２】
フィボナッチベースの記数法は完全であるが一義的ではない。たとえば、フィボナッチ記数法では、十進数１９を表す６つの７桁のベクトルが存在する。
｛０１１１１０１，０１１１１１０，１００１１０１，１００１１１０，１０１０００１，１０１００１０｝
【００５３】
本明細書において定義される場合、二進記数法におけるベクトルは二値ベクトル又は二値コードであり、フィボナッチ記数法におけるベクトルはフィボナッチベクトル、フィボナッチコードワード、又はフィボナッチコードである。同じ数を表すフィボナッチベクトルはすべて等価なベクトルである。
【００５４】
式（７）から、ｍビットフィボナッチベクトルの範囲を以下のように導出する。
ｖ∈［０  ｆｍ＋２）                                                （１３）
【００５５】
個別の値の総数は、ｍビットフィボナッチベクトルを使用して以下のように表すことができる。
ＴｇＮ（ｍ）＝ｆｍ＋２                                              （１４）
【００５６】
禁止パターンなしコードを用いるコーデック
本発明の実施形態は、データをＦＰＦコードに符号化する符号化方法を説明する。この符号化方法は、任意のサイズのバスのためのＦＰＦコーデックの体系的な設計を可能にし、それによって、幅の広いバスを有するコーデックを幅の狭いバスのコーデックから導出することができる。本発明の実施形態によるコーデックの実施態様では、ゲートの数とバス増加との関係は二次的である。比較のために、従来の符号化方法では、この関係は指数関数的である。本発明の符号化方法は、フィボナッチ記数法に基づく。
【００５７】
マッピング
定理１：∃ｄｍｄｍ−１．．．ｄ２ｄ１＝ｖ、ｄｍｄｍ−１.．．ｄ２ｄ１∈Ｎ（Ｆｍ，｛０，１｝）であり、かつＦＰＦである。
∀ｖ∈［０，ｆｍ＋２−１］
【００５８】
定理１は、任意の数ｖ∈［０，ｆｍ＋２−１］に対して、この数を表し、かつ禁止パターンなしである、少なくとも１つのｍビットフィボナッチベクトルｄｍｄｍ−１．．．ｄ２ｄ１＝ｖが存在することを述べている。この証明を付録に記載する。
【００５９】
定理１に従って、入力をそのＦＰＦフィボナッチベクトルにマッピングするコーデックを設計することができる。
【００６０】
近最適ＦＰＦコーデック
本発明の実施形態は、入力データワードをＦＰＦフィボナッチコードに変換する符号化方法を説明する。フィボナッチコードは、必要とされるオーバヘッドが、式（１０）において説明されている論理的な下界よりも１ビット大きいに過ぎないため、近最適である。
【００６１】
本発明の好ましい一実施形態では、符号化器は、その記数法で表されている入力データワード値をフィボナッチ記数法表現に変換する。符号化器の出力は、有効なＦＰＦコードワードであることが保証される。
【００６２】
符号化
図３は、数ｖをＦＰＦフィボナッチベクトル（コード）に符号化する近最適ＦＰＦ−ＣＡＣ符号化方法の擬似コード３００を示している。図４（Ａ）は、本発明の一実施形態による、近最適ＦＰＦ−ＣＡＣ擬似コード３００に基づく符号化器３０の一実施態様を示している。符号化器３０は、ｎビット二値ベクトル４１０、ｖ＝ｂｎ−１.．ｂ０をｍビットＦＰＦフィボナッチベクトル４２０、ｄｍ−１ｄｍ−２．．ｄ０に変換する。符号化器３０の論理構造は、以下のように説明することができる。
１．符号化器は、ｍ−１個のステージを含む。
２．符号化器の各ステージは、１つの符号化ビットを生成する。たとえば、ｋ番目のステージはｄｋ４３０を生成する。
３．各ステージは剰余ｒｋ４４０を生成する。
４．１つのステージの剰余ｒｋ４４０は、後続のステージｋ−１に対する入力である。すなわち、ｋ番目のステージに関して、入力はｄｋ＋１及びｒｋ＋１であり、出力はｄｋ及びｒｋであり、ここで、ｄｋは出力フィボナッチベクトル５２０のうちの１ビットであり、ｒｋは入力ベクトルｖ５１０の剰余であり、これは後続のステージに対する入力である。
５．各ステージｋ、すなわち最上位ビット（ＭＳＢ）ステージを除く任意のステージにおいて、入力ｒｋ＋１が、フィボナッチ数列の対応する２つの連続する要素ｆｋ＋１及びｆｋと比較される（４５０）。ｒｋ＋１≧ｆｋ＋１である場合はｄｋ＝１であり、ｒｋ＋１＜ｆｋである場合はｄｋ＝０であり、そうでない場合はｄｋ＝ｄｋ＋１である。
６．ＭＳＢステージの入力は、コーデックに対する入力、ｖ＝ｂｎｂｎ−１．．ｂ１である。
７．ＭＳＢステージのロジックは、以下のいずれかであり得る。
ｖ≧ｆｋ＋１である場合はｄｋ＝１であり、そうでない場合はｄｋ＝０、又は
ｖ＜ｆｋである場合はｄｋ＝０であり、そうでない場合はｄｋ＝１である。
【００６３】
図５は、符号化器のｋ番目のステージの一実施態様を示しており、ここでｋ＜ｍである。比較動作４５０のための１つの比較器５１０、１つの減算器５２０、及び、選択ライン５３１に従って選択する２対１選択器５３０が存在する。
【００６４】
復号
図４（Ｂ）は、近最適ＦＰＦコード復号動作のための復号器６０を示している。復号器６０は、バス５０上で送信されたフィボナッチ記数法におけるコードワード４２０を、元の記数法、たとえば二値フォーマットにおけるデータワード４１０に逆変換する。本発明の一実施形態では、復号プロセスは式（１２）に基づく。
【００６５】
表ＩＩは、近最適ＦＰＦ−ＣＡＣ擬似コードを使用して生成されるすべての６ビットコードワードを列ＣＯＤＥ−１に示している。
【００６６】
上述のように、ＭＳＢステージは、先行するビットが存在しないため、他のステージとは異なる。グレー領域、すなわち、重複するＦＰＦフィボナッチベクトルが存在する領域内の値に関して、ｄｍ−１を、いずれかの値となるように符号化することができる。近最適ＦＰＦ−ＣＡＣ擬似コードでは、入力値がｍ番目のステージのグレーゾーン内にある場合、ＭＳＢ（ｄｍ）が０になるように符号化することを自由裁量で選択する。ここで、ｋ番目のステージのグレーゾーンは［ｆｋ−１  ｆｋ）の領域として定義される。
【００６７】
グレーゾーン内のすべての値に関してｄｍを１となるように符号化する場合、異なるセットのコードワードが表ＩＩのＣＯＤＥ−２列にリストされる。表ＩＩのＣＯＤＥ−１列及びＣＯＤＥ−２列の両方におけるすべてのコードワードはＦＰＦである。簡潔にするために、ＣＯＤＥ−１にリストされているコードワードとは異なるコードワードのみをＣＯＤＥ−２にリストしている。
【００６８】
【表２】
2009232461.tif 000011
【００６９】
式（１４）に基づいて、ＣＯＤＥ−１及びＣＯＤＥ−２の両方におけるコードワードの総数はｆｍ＋２であると判断し、これは式（５）の２ｆｍ＋１の最大濃度よりもわずかに小さい。上述の符号化方法は、コーデックに必要とされるビット数が、最低限必要なビット数ｍｏｐｔよりも１ビット多いに過ぎないことを要求する。これは、ＴｇＮ（ｍ）＝ｆｍ＋２、Ｔｇ（ｍ）＝２ｆｍ＋１、ＴｇＮ（ｍ＋１）＝ｆｍ＋３、かつｆｍ＋２＜２ｆｍ＋１＜ｆｍ＋３であるためである。
【００７０】
表ＩＩＩは、３ビット〜３２ビットの二値データを符号化するのに必要なビット数を示している。ｎは入力二値バスのビット数を指し、ｍｏｐｔは最適なコードに必要なビット数を指し、ｍｎｏはコーデックに必要なビット数を指し、Δ（ｍ）はｍｎｏとｍｏｐｔとの間の差を指す。
【００７１】
【表３】
2009232461.tif 000012
【００７２】
最適コーデック
上述の近最適コーデックのマッピング方式は、最適なオーバヘッドパフォーマンスを達成するように変更することができる。このようなコーデックを本明細書では「最適コーデック」と呼ぶ。
【００７３】
表ＩＩは、ＣＯＤＥ−１内に含まれていないＣＯＤＥ−２内のコードワードが合計で（ｆｍ＋１−ｆｍ）個存在することを示している。重複するＦＰＦフィボナッチベクトルが存在する領域をグレー領域として定義する。ＣＯＤＥ−１及びＣＯＤＥ−２の両方における個別のコードワードの総数は以下の通りである。
ＴｇＯ（ｍ）＝ｆｍ＋２＋ｆｍ＋１−ｆｍ＝ｆｍ＋１＋ｆｍ＋ｆｍ＋１−ｆｍ＝２ｆｍ＋１                                                                  （１５）
【００７４】
近最適なコードが最大濃度に達しない理由は、グレー領域内の値の冗長なＦＰＦフィボナッチベクトルに起因する。表ＩＶは、本発明の一実施形態において、ＣＯＤＥ−２のグレー領域内のコードワードをＣＯＤＥ−１の上部に移動することによってこの冗長性を除去することを示している。
【００７５】
【表４】
2009232461.tif 000013
【００７６】
冗長性を除去するために、これらのコードワードの値をｆｍ＋２−ｆｍ＝ｆｍ＋１によってシフトする。コーデックのＭＳＢステージは、この値のシフトを新たなマッピング方式に反映するように変更される。
【００７７】
【数８】
2009232461.tif 000014
【００７８】
これに従って、復号器は以下のように変更される。
【００７９】
【数９】
2009232461.tif 000015
【００８０】
表ＩＶは、各コードワードについて、データワード値に対応する、最適コーデックに基づくコードワードを示している。このマッピング方式は、表ＩＶにおける第２列（ＸＢ）に示されているような追加のビットを有するコードワードと解釈することもできる。このビットは、その値をｄｍ及びｄｍ−１の値に基づいて復号器によって復元することができるため、バス上で送信されない。
【００８１】
最適な符号化方式のオーバヘッドパフォーマンスは式（９）において与えられる論理的な下界に達する。
【００８２】
近最適マッピング方式の最適化
近最適マッピング方式を変更して、ＭＳＢステージを単純化することができる。ｂｎｂｎ−１．．．ｂ１を、二値入力ベクトルｄｍ＝ｂｎ及びｒｍ＝ｂｎ−１ｂｎ−２．．．ｂ１とする。変更されたマッピングは以下のように表すことができる。
【００８３】
【数１０】
2009232461.tif 000016
【００８４】
この変更によって、符号化器が入力ＭＳＢビットを出力ＭＳＢビットとして直接出力することが可能となる。この出力は、以下の理由によって、依然としてＦＰＦコードであることが保証される。すなわち、ｎビット二値コードをｍビットフィボナッチコードに符号化するために、ｎ及びｍは２ｎ＜ｆｍ＋２を満たし、２ｎ≦ｆｍ＋２＜２ｆｍ＋１となり、したがって以下の不等式が成り立つためである。
２ｎ−１＜ｆｍ＋１                                                  （１９）
【００８５】
式（１９）は、ｎビット入力二値データをＭＳＢビットと（ｎ−１）ビットベクトルとに分割することができることを示している。ＭＳＢビットは符号化されることなく送信され、ｎ−１ビットベクトルはｍ−１ビットバスに符号化される。
【００８６】
図６は、単純化されたＭＳＢステージを有する変更されたコーデックのブロック図を示している。符号化器６３０において、入力ｂｎ６４０のＭＳＢは、出力ｄｍ６５０のＭＳＢに直接マッピングされる。入力ベクトルの剰余ｂｎ−１ｂｎ−２．．．ｂ１は（ｍ−１）番目のステージの入力となる。
【００８７】
変更された符号化方式の復号器６６０は、図４（Ｂ）に示す復号器６０と同様に、式（１８）に従って実施される。
【００８８】
バス分割
本発明の実施形態をバス分割と組み合わせて使用して、符号化器の全体的な複雑性をさらに低減すると共に、符号化器の速度を増加させることができる。分割を半分低減することによって、バス速度をほぼ４倍増加させることができる。同様に、コーデック回路の総面積は入力ビットの数に対して二次的な関係を有し、したがってバスを分割することによって面積は約５０％低減する。
【００８９】
復号器の構造は、符号化器の構造よりも単純であり、遅延リップル効果を有しない。しかしながら、バス幅が増大すると、総和ステージのサイズも増大し、経験される遅延が増大する。本発明のいくつかの実施形態では、乗算及び論理ＡＮＤ演算は存在しない。ｆｋは定数であるため、ｄｋをｆｋの非ゼロビット位置に関連付ける事例が単純化される。
【００９０】
図７に示される例では、ｎビット入力バス（ｎは偶数）が２つのｎ／２ビットグループ、すなわちｂｎ／２．．ｂ１（グループＡ）７３０と、ｂｎ．．ｂｎ／２＋１（グループＢ）７２０とに分割される。ｂｎ／２．．ｂ１７３０及びｂｎ．．ｂｎ／２＋１７２０は、２つのｋビットＦＰＦバス、ｄａｋ．．ｄａ１及びｄｂｋ．．ｄｂ１に符号化される（７４０及び７４１）。ここでｋは２ｆｋ＋１＞２ｎ／２を満たす。両方のグループＥＮＣ−Ａ７４１及びＥＮＣ−Ｂ７４０の符号化器はｎ／２ビット−ｋビット符号化器である。２つのｋビット−ｎ／２ビット復号器ＤＥＣ−Ａ７５１及びＤＥＣ−Ｂ７５０が受信機側で使用される。すなわち、符号化はラインの各グループに対して独立して実施される。
【００９１】
符号化器の最大遅延はτｅｎｃ（ｎ）ではなくτｅｎｃ（ｎ／２）であり、復号器の最大遅延はτｄｅｃ（ｎ）ではなくτｄｅｃ（ｎ／２）である。コーデックのゲートカウントはＧＣ（ｎ）から２・ＧＣ（ｎ／２）に低減する。グループ境界にわたる禁止パターンの発生を防止するために、追加のワイヤ７１０がバス上に必要とされる。図７の例では、ｄａｋ及びｄｂ１が重複し、したがって、グループ境界におけるバス内のビットは、．．．ｄｂ１ｄｂ１ｄａｋｄａｋｄａｋ−１．．．である。
【００９２】
本発明を好ましい実施形態の例として説明してきたが、本発明の精神及び範囲内でさまざまな他の適合及び変更を行うことができることは理解されたい。したがって、添付の特許請求項の目的は、本発明の真の精神及び範囲内に入るこのような変形及び変更のすべてを包含することである。
【００９３】
付録Ａ．定理１の証明
定理１：
∃    ｄｍｄｍ−１．．．ｄ２ｄ１＝ｖ，ｄｍｄｍ−１.．．ｄ２ｄ１∈Ｎ（Ｆｍ，｛０，１｝），∀ｖ∈［０，ｆｍ＋２−１］
定理１を証明するために、以下の推論を導出する。
推論１：以下の２つのｍビットフィボナッチベクトル、すなわち、ｄｍｄｍ−１．．．ｄ３０１と、ｄｍｄｍ−１．．．ｄ３１０とは等価である。すなわち、ｄｍｄｍ−１．．．ｄ３０１≡ｄｍｄｍ−１．．．ｄ３１０。
証明：ｆ２＝ｆ１＝１であるため、最後の２桁が交換可能であることは明らかである。
推論２：ｍビットフィボナッチベクトルｄｍｄｍ−１．．．ｄ２ｄ１に関して、連続する３ビットｄｋｄｋ−１ｄｋ−２が値１００を有する場合、これらを０１１で置き換えることによって等価なベクトルが生成される。
証明：これは、式（１７）において与えられるフィボナッチ数列の定義に基づいて証明される。
推論３：ｍビットフィボナッチベクトルｄｍｄｍ−１．．．ｄ２ｄ１に関して、ベクトルｄｋｄｋ−１．．．ｄｋ−ｎ内の連続するビット（スライス）の数が、０１０１．．．０１００、すなわち、最後の２ビットを除いて０と１とが交互に現れるパターンを有する場合、このスライスを、パターン００１１．．．１１１１、すなわち、最初の２ビットを除くすべてのビットが１であるパターンに置き換えることによって、等価なベクトルが生成される。
証明：ｄｋ−１ｄｋ−２ｄｋ−３が置き換えられるまで、右から左へ、１００を０１１に（推論２）反復して置き換えることができる。
推論４：ｍビットフィボナッチベクトルｄｍｄｍ−１．．．ｄ２ｄ１に関して、ベクトルｄｋｄｋ−１．．．ｄｋ−ｎ内のスライスが、１０１０．．．１０１１、すなわち、最後の２ビットを除いて０と１とが交互に現れるパターンを有する場合、このスライスを、パターン１１００．．．００００、すなわち、最初の２ビットが１であり、他のビットが０であるパターンに置き換えることによって、等価なベクトルが生成される。
証明：ｄｋ−１ｄｋ−２ｄｋ−３が置き換えられるまで、右から左へ、０１１を１００に（推論２）反復して置き換えることができる。
定理１の証明：
まず、以下を述べておく：
∃  ｄｍｄｍ−１．．．ｄ２ｄ１＝ｖ，ｄｍｄｍ−１.．．ｄ２ｄ１∈Ｎ（Ｆｍ，｛０，１｝），∀ｖ∈［０，ｆｍ＋２−１］
換言すれば、任意の数ｖ∈［０，ｆｍ＋２−１］に関して、少なくとも１つのｍビットフィボナッチベクトルｄｍｄｍ−１．．．ｄ２ｄ１が存在する。これは、フィボナッチ記数法の完全性から得られる。ベクトルｄｍｄｍ−１．．．ｄ２ｄ１がＦＰＦでない場合、以下の手順のいくつか又はすべてを実施することによって、ＦＰＦである少なくとも１つの等価なベクトルを生成することができる。
ベクトルが禁止パターン（１０１又は０１０）で終わる場合、１１０又は００１で終わる等価なベクトルが存在する（推論１）。
ベクトル内の任意のスライス（連続するビットのグループ）が禁止パターンを含む場合、スライスを推論３及び推論４を使用して禁止パターンのないパターンに置き換えることができる。
【００９４】
付録Ｂ：ＦＰＦ符号化アルゴリズムの正確性の証明
証明：
このアルゴリズムの正確性は、最初のｋ個のステージから部分的に生成される出力ベクトルｄｍ．．．ｄｋ＋１ｄｋがＦＰＦである場合に、（ｋ−１）番目のステージの出力ｄｋ−１を加えることによっては禁止パターンはもたらされないことを実証することによって証明することができる。
要素ｄｋ＝ｄｋ＋１である場合、ｄｋ−１の値にかかわらず禁止パターンは生成されない。したがって、ｄｋ≠ｄｋ＋１の場合にｄｋ−１がｄｋ−１＝ｄｋを満たすことを示すことのみが必要である。アルゴリズム２に基づいて、ｄｋが強制的に０又は１にされる場合にのみｄｋ≠ｄｋ＋１となる。この証明は、ｄｋが強制的に１つの特定の値にされるときに、ｄｋ−１がｄｋと同じ値に符号化されることを証明することに軽減される。
以下で、ｄｋが強制的に１にされる場合にｄｋ−１が強制的に０にされないことを証明する。
ｄｋ＝１かつｄｋ≠ｄｋ＋１［ｄｋは強制１ゾーン内にある］
⇒ｒｋ＋１≧ｆｋ＋１かつｒｋ＝ｒｋ＋１−ｆｋ
⇒ｒｋ≧ｆｋ＋１−ｆｋ
⇒ｒｋ≧ｆｋ−１［ｄｋ−１は強制０ゾーン内にない］
⇒ｄｋ−１＝１
以下で、ｄｋが強制的に０にされる場合にｄｋ−１が強制的に１にされないことを証明する。
ｄｋ＝０かつｄｋ≠ｄｋ＋１［ｄｋは強制０ゾーン内にある］
⇒ｒｋ＋１＜ｆｋ＋１かつｒｋ＝ｒｋ＋１
⇒ｒｋ＜ｆｋ［ｄｋ−１は強制１ゾーン内にない］
⇒ｄｋ−１＝０
したがって、符号化アルゴリズムがＦＰＦコードを生成することが保証される。
【図１】
2009232461.tif 000017
【図２】
2009232461.tif 000018
【図３】
2009232461.tif 000019
【図４】
2009232461.tif 000020
【図５】
2009232461.tif 000021
【図６】
2009232461.tif 000022
【図７】
2009232461.tif 000023
【外国語明細書】
2009232461.tif 000024
2009232461.tif 000025
2009232461.tif 000026
2009232461.tif 000027
2009232461.tif 000028
2009232461.tif 000029
2009232461.tif 000030
2009232461.tif 000031
2009232461.tif 000032
2009232461.tif 000033
2009232461.tif 000034
2009232461.tif 000035
2009232461.tif 000036
2009232461.tif 000037
2009232461.tif 000038
2009232461.tif 000039
2009232461.tif 000040
2009232461.tif 000041
2009232461.tif 000042
2009232461.tif 000043
2009232461.tif 000044
2009232461.tif 000045
2009232461.tif 000046
2009232461.tif 000047
2009232461.tif 000048
2009232461.tif 000049
2009232461.tif 000050
2009232461.tif 000051
2009232461.tif 000052
2009232461.tif 000053
2009232461.tif 000054
2009232461.tif 000055
2009232461.tif 000056
2009232461.tif 000057
2009232461.tif 000058
2009232461.tif 000059
2009232461.tif 000060
2009232461.tif 000061
2009232461.tif 000062