定数重みコード

符号理論 において、定重み符号はm -of- n符号とも呼ばれ、すべての符号語が同じハミング重みを共有する誤り検出訂正符号です。ワンホット符号とバランス符号は、広く使用されている 2 種類の定重み符号です。

この理論は、設計理論（ t設計やシュタイナー システムなど）と密接に関連しています。離散数学のこの分野に関する研究のほとんどは、バイナリ定重みコード に関するものです。

バイナリ定重みコードには、GSMネットワークでの周波数ホッピングなど、いくつかの用途があります。 ^[1] ほとんどのバーコードは、バイナリ定重みコードを使用して、黒と白の縞を区別する明るさのしきい値を自動的に設定することを簡素化しています。ほとんどのラインコードは、定重みコード、またはほぼ定重みのペアディスパリティコードのいずれかを使用します。エラー訂正コードとしての使用に加えて、コードワード間の大きなスペースは、遅延に敏感でない回路などの非同期回路の設計にも使用できます。

ベルガー コードのような定重みコードは、すべての一方向エラーを検出できます。

定重み符号に関する中心的な問題は、長さ、ハミング距離、重みのバイナリ定重み符号のコードワードの最大数はいくつであるかということです。この数は と呼ばれます。 ${\displaystyle n}$ ${\displaystyle d}$${\displaystyle w}$${\displaystyle A(n,d,w)}$

いくつかの些細な観察を除けば、これらの数値を簡単な方法で計算することは一般に不可能です。上限は、第1および第 2 ジョンソン境界などのいくつかの重要な定理によって与えられ、^[2]、より良い上限は他の方法で見つかることもあります。下限は、離散数学のさまざまな方法を使用するか、コンピューターによる徹底的な検索を通じて、特定のコードを提示することで最もよく見つかります。このような記録破りのコードの大規模な表は 1990 年に公開されました^[3] 。また、より長いコードへの拡張 (ただし、 GSM アプリケーションに関連するおよびの値のみ) は 2006 年に公開されました^[1]。${\displaystyle d}$${\displaystyle w}$

定重みコードの特殊なケースは、ビットをコードワードのビットにエンコードする 1/ Nコードです。1/2 コードでは、コードワード 01 と 10 を使用して、ビット '0' と '1' をエンコードします。1/4 コードでは、ワード 0001、0010、0100、1000 を使用して、2 つのビット 00、01、10、11 をエンコードします。例としては、デュアル レール エンコーディングや、遅延に敏感でない回路で使用されるチェーン リンク^[4]があります。これらのコードでは、およびです。 ${\displaystyle \log_{2}N}$${\displaystyle N}$${\displaystyle n=N,~d=2,~w=1}$${\displaystyle A(n,d,w)=n}$

ワンホット コードの注目すべき用途としては、 1/2 コードを使用する バイフェーズ マーク コード、 1/ nコードを 使用するパルス位置変調、アドレス デコーダーなど があります。

符号理論において、バランス符号とは、各コードワードに 0 ビットと 1 ビットが同数含まれるバイナリ 前方誤り訂正符号である。バランス符号はドナルド・クヌースによって導入された。^[5]バランス符号は、いわゆる無順序符号のサブセットであり、コードワード内の 1 の位置が他のコードワード内の 1 の位置のサブセットにならないという特性を持つ符号である。すべての無順序符号と同様に、バランス符号は、符号化されたメッセージ内のすべての一方向誤りの検出に適している。バランス符号は、並列に実行できる特に効率的な復号化を可能にする。^{[5] [6] [7]}

バランスウェイト コードの注目すべき用途としては、 1/2 コードを使用する バイフェーズ マーク コード、 4/8 コードを使用する6b/8b エンコーディング、 ofコード (ゼロ コードワードを除く)であるアダマール コード、 three-of-sixコードなどがあります。 ${\displaystyle 2^{k-1}}$${\displaystyle 2^{k}}$

MIPI C-PHYで使用される3線式レーンエンコーディングは、定重みコードを3値に一般化したものと考えることができます。つまり、各線は3値信号を送信し、どの瞬間にも3本の線のうち1本は低信号を送信し、1本は中信号を送信し、1本は高信号を送信しています。^[8]

m -of- nコードは、コード ワード長がnビットの分離可能なエラー検出コードです。各コード ワードには、正確にm個の「1」インスタンスが含まれます。1 ビットのエラーにより、コード ワードにはm + 1 個またはm − 1個の「1」が含まれます。m -of -nコードの例としては、米国郵政公社が使用する2-of-5 コードがあります。

最も単純な実装は、元のデータにm個の 1 が含まれるまで 1 の文字列を追加し、その後 0 を追加して長さnのコードを作成することです。

例：

すでに上で述べたワンホット コードとバランス ウェイト コード以外の、定数ウェイト コードの注目すべき使用法としては、 コード 39での3-of-9 コードの使用、 25 進コード化 10 進コードでの 2-of-7 コード、2-of-5 コードの使用など が挙げられます。

• Andries Brouwerが管理する A ( n , d , w ) {\displaystyle A(n,d,w)} の下限値の表
• A ( n , d , w ) {\displaystyle A(n,d,w)} の上限表は Erik Agrell によって管理されている