(57)【要約】【課題】任意の中立数ｋ（ここで、２（ｎ−１）＜２ｋ＜２ｎであり、ｎは正の整数である）に関して、項目数が２ｋで、ビット数がｎの巡回グレイ・コード（「２ｋグレイ・コード」）の生成を可能にする方法を提供する。【解決手段】反射２進技法によって、ｎ個のビットに２ｎ個の項目コードを作成するステップと、次に、全反射２進コードの最初の半分において最後のｋ個の順序付き項目を選択し、その後、全反射２進コードのもう半分において最初のｋ個の順序付き項目を選択するステップが含まれる。これらの選択された２ｋ個の順序付き項目は短縮されるが、それにもかかわらず、ビット数がｎの巡回（簡約）グレイ・コードである。あるいはまた、全反射２進コードの最初の半分において最初のｋ個の順序付き項目を選択し、その後、全反射２進コードのもう半分において最後のｋ個の順序付き項目を選択することも可能である。【選択図】図１
2006074758.tif 000002
【特許請求の範囲】
【請求項１】
自然数ｋに関して、項目数が２ｋのｎ個のビットによる簡約グレイ・コードを生成する方法であって、
（ａ）（ｎ−１）個のビットによるグレイ・コードであって、そのｒ個の順序付き項目が（ａ，ｂ，ｃ，．．，ｉ，ｊ）である前記グレイ・コードを折り返して、（ａ，ｂ，ｃ，．．，ｉ，ｊ，ｊ，ｉ，．．．，ｃ，ｂ，ａ）である２ｒ個の順序付き項目の中間巡回コードを生成するステップ（ここで、ｒはｋを超え、（．．．，ｂ，ａ，ａ，ｂ，．．．）及び（．．．，ｉ，ｊ，ｊ，ｉ，．．）項目は、項目の順序において対称的逆シーケンスに相当する）と、
（ｂ）前記中間コードの最初の半分において前記順序付き項目（ａ，ｂ，ｃ，．．，ｊ）のそれぞれにおける選択位置に第１のビット値を付加して、ビット数がｎの項目を生成し、前記中間コードのもう半分において前記順序付き項目（ｊ，．．．，ｃ，ｂ，ａ）のそれぞれにおける選択位置に第１のビット値の補数を付加して、ビット数がｎの項目を生成し、前記中間コードの前記最初の半分と前記もう半分の組み合わせ付加バージョンによって、項目数が２ｒの巡回反射２進グレイ・コードが形成されるようにするステップと、
（ｃ）ステップ（ｂ）の項目数が２ｒの前記巡回反射２進グレイ・コードから、対称的逆シーケンスに対応する２（ｒ−ｋ）の連続項目を対称的に廃棄して、ｎビットによる、項目数が２ｋの巡回簡約グレイ・コードが残るようにするステップを有する、方法。
【請求項２】
ステップ（ａ）の（ｎ−１）ビットによる前記グレイ・コードが、それ自体、反射２進グレイ・コードである、請求項１に記載の方法。
【請求項３】
ステップ（ａ）の（ｎ−１）ビットによる前記グレイ・コードが、それ自体、反射２進グレイ・コードであり、２ｋが２（ｎ−１）未満である、請求項１に記載の方法。
【請求項４】
２ｋが２ｎ未満で、２（ｎ−１）を超える、請求項１に記載の方法。
【請求項５】
請求項１に従って生成されるグレイ・コードを組み込んだ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、偶数簡約グレイ・コードの生成方法に関する。
【背景技術】
【０００２】
グレイ・コードは、全て、同じ数のビットを備えている、２進整数の順序付き集合であり、この集合は、その集合に関連した順序で異なる整数に移ると、１ビットだけ変化する特性を備えている。集合内のある項目におけるビットの数値は、アラビア２進数とみなすことができるが、順序は、一般に、その後続要素を求めるため、集合内の項目に１を加えても得られない。極めて実質的な意味において、グレイ・コードは、上述の特定タイプの順序をなすように「考案された」一連の２進整数の構成であり、２つ以上のグレイ・コードが存在する。プログラムで実行されるアルゴリズム演算及び論理演算を利用して、グレイ・コードを生成し、さらに、演算することが可能であり、ハードウェアで実施されるゲート制御によって、グレイ・コード・カウンタを「インクリメント」及び「デクリメント」し、さらに、グレイ・コードと真の２進数の間で変換を行うことも可能であるが、一般に、こうした演算は、実際に算術とはみなされない。
【０００３】
グレイ・コードは、エンコーダにおける曖昧さの制限、個別クロック信号によって制御されるメカニズムの境界を越えた通信のインターフェイス、及び、多数の論理要素が一度に変化する（例えば、００１１１１から０１００００への遷移）ことによって生じる可能性のある、電源及びアースにおけるノイズまたはグリッチ発生の制限に役立つ。高速データ通信回路要素の場合、用いられるグレイ・コードは、例えば、特定のグレイ・コードを利用し有限状態機械にアドレス指定するためにカウントするカウンタのような、ハードウェアに導入するのが一般的である。
【０００４】
「標準」グレイ・コードと呼ばれることが多い特定のグレイ・コードが存在する。これは、厳密には反射２進コード(a reflected binary code)と呼ばれるコード・クラスの一般的な例である。反射２進コードは、巡回コードであり、ほとんど、ｎ個のビットに関して最大で２ｎの異なる項目を備えている。（「巡回」の意味するところは、その順序における「最初」と「最後」の項目が、やはり１ビットだけ離れており、その順序が「循環して」、もう一度やり直すということである。）これらの反射２進コードについて初めて取上げたのは、特許文献１であると思われる。その後、「標準」及び別様のグレイ・コードが、かなり着目されるようになった。例えば、非特許文献１、２、及び、３を参照されたい。ウェブサイト（例えば、非特許文献４及び５参照）を素早く閲覧してみても明らかになるように、グレイ・コードは、多種多様な分野において用途がいっそう広がっている。
【０００５】
グレイ・コードを発見または生成するための従来の技法は、項目数が２ｎのコードに制限されるが、ここで、ｎは各整数のビット数である。これは、もっと項目数の少ないグレイ・コードで十分とする用途が存在するので、残念なことである。しかし、２ｎのグレイ・コードの部分集合の大部分は、巡回コードではなく、その有用性をかなり妨げる可能性のある欠点である。２ｎの全項目を必要としない用途の場合、項目が２ｎ未満の巡回グレイ・コードを生成するための信頼できる方法によって、ハードウェア及び電力消費が節約されることになる。もちろん、２ｎ未満の項目の意味するところは、２の全累乗が、実際に必要とするｎビット・グレイ・コード内の項目数より多く、ある項目数ｍ（ここで、２（ｎ−１）＜ｍ＜２ｎ）でちょうどうまくいくということである。従って、問題は、「項目数がｍで、ビット数がｎの巡回グレイ・コードをいかにして見つけることができるか？」ということである。
【特許文献１】米国特許第２，６３２，０５８号明細書
【非特許文献１】Ｍｏｎｔｇｏｍｅｒｙ  Ｐｈｉｓｔｅｒ著、Ｊｒ．、Ａｐｐｅｎｄｉｘ  ＩＩ  ｉｎ  「ＬＯＧＩＣＡＬ  ＤＥＳＩＧＮ  ＯＦ  ＤＩＧＩＴＡＬ  ＣＯＭＰＵＴＥＲＳ」、第８版、Ｊｏｈｎ  Ｗｉｌｅｙ  ＆  Ｓｏｎｓ、１９９６年
【非特許文献２】Ｒｅｉｎｇｏｌｄ、Ｎｉｅｖｅｒｇｌｅｔ、及び、Ｄｅｏ著、§５．２（Ｓｕｂｓｅｔｓ  ｏｆ  Ｓｅｔｓ）  ｉｎ  「Ｃｏｍｂｉｎａｔｏｒｉａｌ  Ａｌｇｏｒｉｔｈｍｓ：Ｔｈｅｏｒｙ  ａｎｄ  Ｐｒａｃｔｉｃｅ」、Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ、１９７７年（ＩＳＢＮ  ０−１３−１５２４４７−Ｘ）
【非特許文献３】§２０．２  ｉｎ  「ＮＵＭＥＲＩＣＡＬ  ＲＥＣＩＰＥＳ  ＩＮ  Ｃ：ＴＨＥ  ＡＲＴ  ＯＦ  ＳＣＩＥＮＴＩＦＩＣ  ＣＯＭＰＵＴＩＮＧ」、Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ、１９９２年（ＩＳＢＮ  ０−５２１−４３１０８−５）
【非特許文献４】＜ＵＲＬ：ｈｔｔｐ：／／ｗｗｗ．ｎｉｓｔ．ｇｏｖ／ｄａｄｓ／ＨＴＭＬ／ｇｒａｙｃｏｄｅ．ｈｔｍｌ＞
【非特許文献５】＜ＵＲＬ：ｈｔｔｐ：／／ｗｗｗ．ｃｓ．ｂｈａｍ．ａｃ．ｕｋ／Ｍｉｒｒｏｒｓ／ｆｔｐ．ｄｅ．ｕｕ．ｎｅｔ／ＥＣ／ｃｌｉｆｅ／ｗｗｗ／Ｑ２１．ｈｔｍ＞
【発明の開示】
【発明が解決しようとする課題】
【０００６】
項目が２ｎ未満で、ビット数がｎの巡回グレイ・コードを見つける問題方法を提供する。
【課題を解決するための手段】
【０００７】
項目が２ｎ未満で、ビット数がｎの巡回グレイ・コードを見つける問題に対する解決法は、任意の中立数ｋ（ここで、２（ｎ−１）＜２ｋ＜２ｎであり、ｎは正の整数である）に関して、項目数が２ｋで、ビット数がｎの巡回グレイ・コード（「２ｋグレイ・コード」）の生成を可能にする開示のアルゴリズムによって得られる。こうしたグレイ・コードを「簡約」(“reduced”)グレイ・コードと呼ぶことにする。要するに、この方法には、反射２進技法によって、ｎ個のビットに２ｎ個の項目コードを作成するステップと、次に、全反射２進コードの最初の半分において最後のｋ個の順序付き項目を選択し、その後、全反射２進コードのもう半分において最初のｋ個の順序付き項目を選択するステップが含まれる。これらの選択された２ｋ個の順序付き項目は短縮されるが、それにもかかわらず、ビット数がｎの巡回（簡約）グレイ・コードである。あるいはまた、全反射２進コードの最初の半分において最初のｋ個の順序付き項目を選択し、その後、全反射２進コードのもう半分において最後のｋ個の順序付き項目を選択することも可能である。グレイ・コードが、その欄がビット位置であり、その行がコード項目であるテーブルとして表される場合、オプションにより、２ｋ個の選択の前または後に、欄全体を随意に交換して、表向きは「反射」コードには見えない、異なる追加巡回簡約グレイ・コードが得られるようにすることが可能である。巡回簡約グレイ・コードが識別されると、ハードウェア（例えば、カウンタ、グレイ／２進変換器）によるそのゲート・レベル回路の実現は、例えば、コード内の項目を互いに関連づける方法（例えば、シーケンス、マッピング）、及び、任意の加えられる制御信号に関連づける（例えば、インクリメント、デクリメント）方法に関するＶｅｒｉｌｏｇによる記述によって駆動される、ＳｙｎｏｐｓｙｓまたはＳｉｍｐｌｉｆｙのような標準合成ツールを用いて容易に達成される。
【発明を実施するための最良の形態】
【０００８】
ｎのビットと２ｎの状態の反射２進コードを作成する方法について考察することから開始する。さまざまな説明または手法が存在するが、前述のｗｗｗ．ｎｉｓｔ．ｇｏｖウェブサイトから下記の１つを得た。
【０００９】
ｎビットでグレイ・コードを作成する方法の１つは、ｎ−１のビットに関して１から始めることである。例えば、２ビットに関するグレイ・コードから始めることにする（この例及び後続の例において、序数の状態数（Ｓｉ）は、各グレイ・コード項目の左に示される）。
【表１】
2006074758.tif 000003
【００１０】
次に、下記では、ｎ−１ビットに関するグレイ・コード自体を、ただし、逆順に繰り返す。
【表２】
2006074758.tif 000004
【００１１】
次に、最初の半分、すなわち上半分の左に０または１を付加し、さらに、もう半分、すなわち下半分の左に１または０（０または１の補数）を付加する。
【表３】
2006074758.tif 000005
【００１２】
結果は、２つの反射２進３ビット・グレイ・コードである。もちろん、異なる２ビット・コード（００，１０，１１，０１）から開始することも可能である。また、少なくとも読者が、反射２進グレイ・コードが唯一のグレイ・コードであると誤って信じてしまわないように、２つの非反射３ビット・グレイ・コードを以下に列挙する。
【表４】
2006074758.tif 000006
【００１３】
しかし、（ｅ）または（ｆ）は、４ビット反射２進グレイ・コードを生成するための開始点として利用することが可能である。明らかに、グレイ・コードの大ファミリが存在し、反射２進グレイ・コードは、単なるそのファミリの部分集合である。（反射グレイ・コードから非反射グレイ・コードを得るのは困難ではなく、最も左の欄をどれか他の欄と交換するだけである。それが、（ｃ）から（ｆ）を得た方法である。最も左の欄と中央の欄が交換された。）
次に、さらに続ける前に、指摘しておくべきことがいくつかある。開始したさまざまなグレイ・コード例（ａ）、（ｃ）、及び、（ｄ）は、全て、重要な特性を共有している。順序付き集合の中央に関して対応対をなすように、いかにコードを配置することが可能であるかについて注意されたい。すなわち、（ａ）の場合Ｓ１とＳ２の対及びＳ０とＳ３の対、同様に、（ｃ）及び（ｄ）に関するＳ３／Ｓ４、Ｓ２／Ｓ５、Ｓ１／Ｓ６、及び、Ｓ０／Ｓ７。この対応の内容は、関与するコード項目が、グレイ・コード内において、互いに先行または後続することができるということである。それは、１つのコード項目を他のコード項目と交換することができるという意味ではなく、こうした対が、他の部分を廃棄した後に残るであろう、簡約グレイ・コードの他の２つのセグメントを結合する「接合部」になることが可能であるという意味である。すなわち、この特性によって、グレイ・コードを短縮し、その巡回性を保つための方法が得られる。中点値に関するこの対応対の特性を「平衡」と呼ぶことにし、例（ａ）、（ｃ）、及び、（ｄ）は、平衡グレイ・コードの例であると言うことにする。
【００１４】
実用的なグレイ・コードの例は、どれも、有限であり、回転する球体の軸に２つの極があるのとちょうど同じように、「平衡」の概念によって、平衡状態を観測できる第２の遷移が存在するという保証が得られる。従って、（ｃ）の平衡がとれるのは、中点値遷移Ｓ３／Ｓ４についてだけではなく、Ｓ７／Ｓ０についても平衡がとれる。こうした平衡位置のいずれの側にも、「対称的逆シーケンス」と呼ぶことが可能なものを形成する、コード対が存在すると言える。従って、図１について簡単に考察すると、グレイ・コード１のＳ０／Ｓ１５、Ｓ１／Ｓ１４、及び、Ｓ２／Ｓ１３が、対称的逆シーケンスであり、図２のグレイ・コード９のＳ７／Ｓ８、及びＳ６／Ｓ９も対称的逆シーケンスである。
【００１５】
ちょっと考えてみれば、読者は、どの反射２進グレイ・コードも上述のように平衡がとれており、対称的逆シーケンスを含んでいるという点に納得がいくであろう。これは、逆順にそれ自体より下でコードを反復するミラー作用のためにそうなる。しかし、全てのグレイ・コードの平衡がとれるものと考えてはならない。例（ｅ）の場合、Ｓ２／Ｓ５は、グレイ・コードにおいて隣接しているとして対にすることはできない。明らかに、（ｅ）は反射でもなかった。しかし、それでも、（ｅ）の３ビット８状態のグレイ・コードを反射２進グレイ・コード作成プロセス（ａ）〜（ｄ）の開始位置として利用し、平衡のとれた、対称的逆シーケンスを含む１６状態４ビットのグレイ・コードを生成することが可能である。
【００１６】
次に図１を参照すると、それぞれ、４ビットのコード項目で表わされた、１０の状態を有する簡約偶数グレイ・コードの生成方法の説明が示されている。それは、「標準」グレイ・コード１から始まり、この例では、上述の反射２進グレイ・コード作成プロセスの種まきに用いられる（ｃ）であった。グレイ・コード１は、反射コードとして、Ｓ７とＳ８の間の遷移２である、その中央に関して平衡がとれているという点に言及しておくことにする。１０状態の簡約グレイ・コードが望まれるので、遷移２の直前に５つの状態Ｓ３〜Ｓ７を選択し、遷移２の直後に５つの状態Ｓ８〜Ｓ１２を選択することによって、全部で１０の状態Ｓ３〜Ｓ１２になる。これによって、３つの初期状態５  Ｓ１〜Ｓ２と３つの最終状態６  Ｓ１３〜Ｓ１５が未使用のままにしておかれる。グレイ・コード１は平衡がとれているので、選択された状態３及び４の和集合も巡回グレイ・コードである。すなわち、（旧）Ｓ３及び（旧）Ｓ１２は、グレイ・コードにおける隣接項目とすることが可能である。これら１０の状態に（新）Ｓ０〜Ｓ９の番号をつけ直し、１０状態４ビットの簡約グレイ・コード表（７）に示すように、所望の簡約グレイ・コード８として用いることにする。
【００１７】
次に、図２を参照すると、図１の方法のさらなる説明が示されている。この場合、４ビットによる１２状態の簡約グレイ・コードが探索され、同じ一般的な方法が用いられるが、いくつかの相違点がある。まず、図２の開始点として用いられるグレイ・コード９は、図１で用いられるのと同じグレイ・コード（１）ではない。それは、入門的教科書及び論文の説明例においてよく用いられる「標準」グレイ・コードではない。それよりむしろ、前述の３ビット非反射グレイ・コード（ｅ）として開始された。（ｆ）で開始するように選択することも可能であったかもしれない。いずれにせよ、反射２進コード技法を（ｅ）に適用して、４ビットによる平衡のとれた１６状態の巡回グレイ・コード（９）が生成された。１２状態の簡約グレイ・コードを生成するため、４つの状態、すなわち、もとのグレイ・コード９における中央（Ｓ７／Ｓ８）遷移の上の２つ（１０）と、その下の２つ（１１）を廃棄した。結果は、１２状態の簡約グレイ・コード１２である。
【００１８】
読者には明らかなように、図１と図２の本質的な相違は、結果得られる簡約グレイ・コードにおける状態数というよりは、むしろ廃棄された状態の位置である。コードを表として例示する通常のやり方に関連して、異なる簡約グレイ・コードは、（もとの及び非簡約）表における異なる箇所に配置された「平衡点」である遷移に関して対称的逆シーケンスの構成要素を廃棄することによって形成される。反射２進グレイ・コードは、巡回コードであるため、平衡点が表形式の表示のどこに位置するかは、ただ単に、もとの表において最初にどのコード項目を選択するかによって決まる。もちろん、結果生じる簡約グレイ・コードは巡回コードであるため、いくつかの表形式の表示がある。
【００１９】
一般に、ｎビットによる、コード項目数が２ｋの簡約グレイ・コードを見つけるため、（ｎ−１）ビットのグレイ・コードから始めて、２ｎ項目の関連する巡回反射２進コードを生成する。次に、対称的逆シーケンスに属する、ある数ｑのコード項目対を対称的に廃棄すると、項目数が２ｋの巡回簡約グレイ・コードが残る。ここで、２（ｑ＋ｋ）＝２ｎである。
【００２０】
さて、最後に、図３を参照する。図３は、簡約グレイ・コードを組み込んだ、特定のハードウェア装置の略ブロック図である。いくつかのファイバ・チャネルデータ通信構成では、弾性ＦＩＦＯ（先入れ先出し素子）は、重要な要素である。ＦＩＦＯは、クロック領域の境界を越えて１０ビット幅のデータを接続する。ＦＩＦＯは、各組が１ワードのデータを納めるのに十分な大きさの、１２組のフリップ・フロップの配列から構成される。１２状態の２進書き込みカウンタ（１８）は、ＦＩＦＯ書き込みクロックに応答して、入力データに関するＦＩＦＯ位置を決定する。１２状態読み取りカウンタは、ＦＩＦＯ読み取りクロックに応答して、データ出力に用いられるＦＩＦＯ位置を決定する。これら２つのカウンタを互いに比較して（１７）、操作の他の態様に関連した制御信号（不図示）が生成される。
【００２１】
クロック領域の境界を越えて電気的ノイズ及び準安定性エラーを低減するため、２進読み取りカウントが、１２状態簡約グレイ・コードに変換され（１４）、その後、ＦＩＦＯ書き込みクロックとの同期がとられる（１５）。同期後、グレイ・コードは、変換されて、２進数に戻り（１６）、比較される（１７）。
【００２２】
始めから、グレイ・コードでカウントするカウンタを利用し、グレイ・コードと２進数間における変換無しで済ます関連構成によって、同じハードウェア機能性を実現することも可能であるのは明らかである。しかし、グレイ・コードではなく、２進数による数値比較を実施するほうが容易であると思われる場合には、変換が役立つ可能性がある。
【図面の簡単な説明】
【００２３】
【図１】４ビットによる１０状態の簡約２ｋグレイ・コードの生成例を示す図である。
【図２】４ビットによる１２状態簡約グレイ・コードの生成例を示すが、その欄も反射２進コードと異なるように再構成された図である。
【図３】入力及び出力データが、待ち行列に入れられ、ＦＩＦＯ（先入れ先出し）方式で検索されるデータ通信環境において、簡約グレイ・コードを利用することが可能な方法を例示した、略ハードウェア・ブロック図である。
【符号の説明】
【００２４】
１４  偶数サイズ２進数・簡約グレイ・コード変換器
１６  簡約グレイ・コード・２進数変換器
【図１】
2006074758.tif 000007
【図２】
2006074758.tif 000008
【図３】
2006074758.tif 000009