|
|
| 1行目: |
1行目: |
| − | {| class="floatright" border="1" cellpadding="5" style="width: 11em; background: white; border-collapse: collapse;"
| |
| − | |-
| |
| − | | <small>'''2ビット グレイコード'''</small>
| |
| − | 00
| |
| − | 01
| |
| − | 11
| |
| − | 10
| |
| − | |-
| |
| − | | <small>'''3ビット グレイコード'''</small>
| |
| − | 000
| |
| − | 001
| |
| − | 011
| |
| − | 010
| |
| − | 110
| |
| − | 111
| |
| − | 101
| |
| − | 100
| |
| − | |-
| |
| − | | <small>'''4ビット グレイコード'''</small>
| |
| − | 0000
| |
| − | 0001
| |
| − | 0011
| |
| − | 0010
| |
| − | 0110
| |
| − | 0111
| |
| − | 0101
| |
| − | 0100
| |
| − | 1100
| |
| − | 1101
| |
| − | 1111
| |
| − | 1110
| |
| − | 1010
| |
| − | 1011
| |
| − | 1001
| |
| − | 1000
| |
| − | |}
| |
| | | | |
| − | '''グレイコード'''（{{lang-en-short|Gray code}}、'''交番二進符号'''（こうばんにしんふごう、英：{{lang|en|Reflected Binary Code}}などとも）とは、数値の符号化法のひとつで、前後に隣接する符号間の[[ハミング距離]]が必ず1であるという特性を持つ。[[ディジタル回路]]や、具体例としては[[ロータリエンコーダ|アブソリュート・ロータリー・エンコーダー]]のセンサー出力等に使われる。 | + | '''グレイコード'''（{{lang-en-short|Gray code}}、'''交番二進符号'''（こうばんにしんふごう、英：{{lang|en|Reflected Binary Code}}などとも） |
| | | | |
| − | <!--交番二進符号の名は--><!-- ← 「フランク・グレイが1947年の特許出願書」に「交番二進符号」とあるわけがない-->Reflected Binary Codeという表現は[[ベル研究所]]のフランク・グレイ（Frank Gray）による1947年の特許出願書にある<ref>{{US patent|2632058}}、F. Gray. ''Pulse code communication'', March 17, 1953 (filed Nov. 1947).</ref>。1953年に他の人物が提出した特許出願書ではグレイコードと呼ばれている<ref name="pat1">{{US patent|2733432}}、J. Breckman. ''Encoding Circuit'', Jan 31, 1956 (filed Dec. 1953).</ref><ref name="pat2">{{US patent|2823345}}、E. A. Ragland et al. ''Direction-Sensitive Binary Code Position Control System'', Feb. 11, 1958 (filed Oct. 1953).</ref>ほか、他の呼称も使われている<ref name="pat2" />。人名に由来するのであって「灰色コード」ではないため、grey code（灰色を意味するグレイはgreyともgrayとも綴る）と書くのは誤りである。
| + | グレイコード，交番2進コード：2進表示で，連続する数が互いにただ1桁(けた)においてだけ異なるように作られた体系. |
| − | | |
| − | == 通常の二進表現との相互の変換 ==
| |
| − | 通常の二進表現をグレイコードに変換するには、「対象の二進表現」と、「それを１ビット右シフトし、先頭に０をつけたもの」との[[排他的論理和]]をとる。例えば、変換したい対象が10（十進法で）であれば、[[二進法]]で表現すれば「1010」であるから、それと「0101」との排他的論理和をとった、「1111」がグレイコードによる表現である。<!--最上位桁から1であれば残り下桁を反転、0であれば残り下桁を変化させない。-->プログラミング言語では、例えば[[C言語]]では、<code>v ^ (v >> 1)</code> となる。
| |
| − | | |
| − | 逆にグレイコードを通常の二進表現に変換するには、「グレイコードによる表現」の最上位桁から順に最下位桁へ向かって隣の桁との[[排他的論理和]]をとる。(ただし最上位桁のみその値を適用する。)例えば、グレイコードによる表現が「1111」であれば、最上位桁から「1」、その値(1)と次の桁(1)との[[排他的論理和]]をとり「0」、その値(0)と次の桁(1)との[[排他的論理和]]をとり「1」、その値(1)と次の桁(1)との[[排他的論理和]]をとり「0」、と順次各桁を確定し、「1010」が[[二進法]]による表現である。
| |
| − | | |
| − | == 利点 ==
| |
| − | グレイコードは、ある値から隣接した値に変化する際に、常に1ビットしか変化しないという点が利用される。
| |
| − | | |
| − | 一般的な二進法では、隣接する値に移行する際は、最下位桁だけが 0←→1 の入れ替えになる場合を除き、一般に1個以上のビットが変化する。たとえば3から4に変化する場合、011から100に、3個のビットが変化する。
| |
| − | | |
| − | 絶対的な角度をディジタル値で出力するアブソリュート・ロータリー・エンコーダーのような機器において、機械的な接点などで電気信号のオンオフを行う場合を考えてみよう。この場合、機械の動作やデータ読み出しのタイミングによっては、誤ったデータが得られる可能性がある。たとえば011から100に変化する際に、短時間の間に次のように出力が遷移するかもしれない。
| |
| − | | |
| − | {{indent|011 → 010 → 000 → 100}}
| |
| − | | |
| − | 各ビットとも、変化に誤りはないのであるが、機械構造の精度上の問題で、完璧に同時に全ビットが変化することは保証できないのである。そのため遷移の途中の段階でデータを読み出すと、010（2）や000（0）といった偽データを取得してしまう可能性がある。
| |
| − | | |
| − | 一般的な二進法ではなく、グレイコードを使えば、隣接値への変化の際に、常に1ビットしか変わらないので（3から4の変化であれば010から110）、いかなるタイミングで読み出そうとデータの値は以前の値か次の値であり、偽データが生成されることはない。
| |
| − | | |
| − | == 実践的利用 ==
| |
| − | === ハノイの塔 ===
| |
| − | [[ハノイの塔]]においてグレイコードによって表記された数字の一番下の桁に一番小さい円盤、次の数字に二番目の円盤というようにすべての桁と円盤を対応付けたとき、数字が変化することによって変わるビットに対応する円盤を動かすことで解答が求められる。
| |
| − | | |
| − | === 遺伝的アルゴリズム ===
| |
| − | [[遺伝的アルゴリズム]]や分布推定アルゴリズムなどにおいて、数値を表現するのに、グレイコードが使われることがある。多くの場合、結果が改善される。
| |
| − | | |
| − | === ロータリエンコーダ ===
| |
| − | [[File:Encoder Disc (3-Bit).svg|left|thumb|100px]]
| |
| − | 電気接点式の[[ロータリエンコーダ]]について考える。
| |
| − | | |
| − | 金属などの導体をむき出しにしたパターンを円盤に付け、それを複数のブラシで読み取り角度を得るものとする。この時、角度が変化して丁度境目の部分にブラシがあると、接触が不安定で、読み取りデータが1になるかもしれないし0になるかもしれない。しかし、左の図のようにグレイコードを基にしたパターンを使用すれば、不安定になるビットは必ず1ビットだけであり、角度の検出としては安定した結果を得られる。{{-}}
| |
| − | | |
| − | === 実数の表現 ===
| |
| − | 数学的には、[[実数]]の 10 の表現には 10.000000... と 9.999999... の 2 通りがある（一般に、任意の有限[[小数]]は、このような二通りの無限小数として表現できる）。二進法では、1010.000000... と 1001.111111... の 2 種類があることになるが、この時、ある桁から下が、0 と 1 が反転したパターンになってしまう。これを、グレイコードを使って、最初の一桁だけが不定となった後、残りの桁は一致するように表現できる<ref>[http://www.i.h.kyoto-u.ac.jp/~tsuiki/bit/gray.html グレイコードと実数 立木秀樹]</ref>。
| |
| − | | |
| − | === 位相偏移変調(PSK) ===
| |
| − | [[位相偏移変調]]において、差動(差分)位相偏移変調(DPSK)や四位相偏移変調(QPSK)のアルゴリズムに応用されている。
| |
| − | | |
| − | == ｎ進グレイコード ==
| |
| − | {| border="0" cellpadding="10" align="right"
| |
| − | |-
| |
| − | | <!-- Second table to provide spacing around the inner table, can't get it otherwise… -->
| |
| − | {| width="150" align="right" cellpadding="5" border="1" style="border-collapse: collapse;"
| |
| − | |-
| |
| − | | <small>'''通常の三進法 ->
| |
| − | 三進グレイコード'''</small>
| |
| − | {{0}}{{0}}0 -> 000
| |
| − | {{0}}{{0}}1 -> 001
| |
| − | {{0}}{{0}}2 -> 002
| |
| − | {{0}}10 -> 012
| |
| − | {{0}}11 -> 010
| |
| − | {{0}}12 -> 011
| |
| − | {{0}}20 -> 021
| |
| − | {{0}}21 -> 022
| |
| − | {{0}}22 -> 020
| |
| − | 100 -> 120
| |
| − | 101 -> 121
| |
| − | 102 -> 122
| |
| − | 110 -> 102
| |
| − | 111 -> 100
| |
| − | 112 -> 101
| |
| − | 120 -> 111
| |
| − | 121 -> 112
| |
| − | 122 -> 110
| |
| − | 200 -> 210
| |
| − | 201 -> 211
| |
| − | 202 -> 212
| |
| − | 210 -> 222
| |
| − | 211 -> 220
| |
| − | 212 -> 221
| |
| − | 220 -> 201
| |
| − | 221 -> 202
| |
| − | 222 -> 200
| |
| − | |}
| |
| − | |}
| |
| − | '''ｎ進グレイコード'''（{{lang-en-short|n-ary Gray code}} '''ｎ進グレイ符号'''）とは'''交番ｎ進符号'''（こうばんえぬしんふごう）、'''ノンブーリアングレイコード'''({{lang-en-short|non-Boolean Gray code}} '''ノンブーリアングレイ符号'''）ともいい、グレイコードの二進法からｎ進法（[[位取り記数法]])への拡張である。
| |
| − | | |
| − | (n, k)グレイコードはｎ進グレイコードのｋビットでの表記を意味する。
| |
| − | | |
| − | [[三進法]]での拡張グレイコード、三進グレイコードでは０、１、２を用いる。2ビットでは{00, 01, 02, 12, 10, 11, 21, 22, 20}である。
| |
| − | | |
| − | == 十進に特化した符号化 ==
| |
| − | 前後に隣接する符号間のハミング距離が必ず1であるという特性を持つ符号化は、グレイコードだけではない。ここでは、十進法との相性を考慮した符号化である、Glixon code、O'Brien codes、Petherick code、Tompkins codeを紹介する。
| |
| − | {| class="wikitable"
| |
| − | |+
| |
| − | ! 十進表記 !! 二進表記 !! Gray code !! Glixon code !! O'Brien code I !! O'Brien code II !! Petherick code !! Tompkins code
| |
| − | |-
| |
| − | ! 0
| |
| − | | 0000 || 0000 || 0000 || 0000 || 0001 || 0101 || 0010
| |
| − | |-
| |
| − | ! 1
| |
| − | | 0001 || 0001 || 0001 || 0001 || 0011 || 0001 || 0011
| |
| − | |-
| |
| − | ! 2
| |
| − | | 0010 || 0011 || 0011 || 0011 || 0010 || 0011 || 0111
| |
| − | |-
| |
| − | ! 3
| |
| − | | 0011 || 0010 || 0010 || 0010 || 0110 || 0010 || 0101
| |
| − | |-
| |
| − | ! 4
| |
| − | | 0100 || 0110 || 0110 || 0110 || 0100 || 0110 || 0100
| |
| − | |-
| |
| − | ! 5
| |
| − | | 0101 || 0111 || 0111 || 1110 || 1100 || 1110 || 1100
| |
| − | |-
| |
| − | ! 6
| |
| − | | 0110 || 0101 || 0101 || 1010 || 1110 || 1010 || 1101
| |
| − | |-
| |
| − | ! 7
| |
| − | | 0111 || 0100 || 0100 || 1011 || 1010 || 1011 || 1001
| |
| − | |-
| |
| − | ! 8
| |
| − | | 1000 || 1100 || 1100 || 1001 || 1011 || 1001 || 1011
| |
| − | |-
| |
| − | ! 9
| |
| − | | 1001 || 1101 || 1000 || 1000 || 1001 || 1101 || 1010
| |
| − | |}
| |
| − | === Glixon code ===
| |
| − | グレイコードとほぼ同じであるが、9に対応する符号はグレイコードが「1101」である一方、 Glixon code では「1000」となっている。これにより、9と0の変化においてもハミング距離が1となる。
| |
| − | | |
| − | === O'Brien codes ===
| |
| − | Glixon code と同様、9と0の変化においてもハミング距離が1となる。0に対して「0000」を対応させない符号化の1つ。
| |
| − | 最上位ビットを反転させることで、9の補数（''n''に対して''10-n''）となるような符号化の１つ。
| |
| − | | |
| − | === Petherick code ===
| |
| − | Glixon code と同様、9と0の変化においてもハミング距離が1となる。0に対して「0000」を対応させない符号化の1つ。
| |
| − | 最上位ビットを反転させることで、9の補数（''n''に対して''10-n''）となるような符号化の１つ。
| |
| − | | |
| − | === Tompkins code ===
| |
| − | Glixon code と同様、9と0の変化においてもハミング距離が1となる。0に対して「0000」を対応させない符号化の1つ。
| |
| − | 最上位ビットを反転させることで、9の補数（''n''に対して''10-n''）となるような符号化の１つ。
| |
| − | さらに、最下位ビット以外の全てのビットにおいて、1である割合が1/2となっている（最下位ビットは6/10の割合で1である）。
| |
| − | | |
| − | == 脚注 ==
| |
| − | {{Reflist}}
| |
| | | | |
| | + | 20世紀の米国の物理学者 Frank Gray の名にちなむ. |
| | {{DEFAULTSORT:くれいこと}} | | {{DEFAULTSORT:くれいこと}} |
| − | {{Computer-stub}} | + | {{テンプレート:20180815sk}} |
| | | | |
| | [[Category:データ転送]] | | [[Category:データ転送]] |
| | [[Category:コンピュータの算術]] | | [[Category:コンピュータの算術]] |
| | [[Category:数学に関する記事]] | | [[Category:数学に関する記事]] |