このページの翻訳は最新ではありません。ここをクリックして、英語の最新版を参照してください。

誤りの検出と訂正

巡回冗長検査符号

• CRC 符号の機能

• CRC 非直接アルゴリズム

• CRC 非直接アルゴリズムの使用例

• CRC 直接アルゴリズム

• CRC 符号化の参考文献

CRC 符号の機能

巡回冗長検査 (CRC) 符号化は、メッセージが送信されるときに発生する誤りを検出するための誤り制御符号化手法です。ブロック符号や畳み込み符号とは異なり、CRC 符号には組み込みの誤り訂正能力がありません。代わりに、通信システムが受信メッセージのワードに誤りを検出すると、受信側はメッセージ ワードを再送信するよう送信側に要求します。

CRC 符号化では、送信側で各メッセージ ワードに規則が適用され、"チェックサム" または "シンドローム" という余分なビットが作成され、チェックサムがメッセージ ワードに追加されます。送信されたワードを受信した後、受信側は受信したワードに同じ規則を適用します。結果のチェックサムが 0 以外である場合、誤りが発生しているので、送信側はメッセージ ワードを再送信する必要があります。

メインの Communications Toolbox™ ブロック ライブラリで Error Detection and Correction ライブラリのアイコンをダブルクリックして、このライブラリを開きます。誤りの検出と訂正のライブラリで CRC サブライブラリのアイコンをダブルクリックして CRC サブライブラリを開きます。

Communications Toolbox は、Simulink^® ブロック、System object、または MATLAB^® オブジェクトを使用した CRC 符号化をサポートしています。これらの CRC 符号化機能は、誤りの検出と訂正にリストされています。

CRC 非直接アルゴリズム

CRC 非直接アルゴリズムは、多項式 M に対応するバイナリ データ ベクトルを受け取り、多項式 C に対応する r ビットのチェックサムを追加します。x^r による乗算は入力ベクトルを左側に r ビット シフトすることに相当するので、入力ベクトルとチェックサムの連結は、多項式 T = M*x^r + C に対応します。アルゴリズムは、T が次数 r の定義済み多項式 P (生成多項式) によって除算されるように C を選択します。

アルゴリズムは、T を P で除算し、チェックサムを剰余に対応するバイナリ ベクトルに等しくなるように設定します。したがって、T = Q*P + R の場合 (ここで、R は r より小さい次数の多項式)、チェックサムは R に対応するバイナリ ベクトルです。アルゴリズムは、チェックサムの長さが r になるように、必要に応じてチェックサムの先頭に 0 を追加します。

CRC アルゴリズムの伝送位相を実装する CRC 生成機能は、以下の処理を行います。

1. 入力データ ベクトルを r ビットだけ左にシフトし、対応する多項式を P で除算します。

2. チェックサムを長さ r (ステップ 1 の剰余に相当) のバイナリ ベクトルと等しくなるように設定します。

3. チェックサムを入力データ ベクトルに追加します。結果は出力ベクトルです。

先に説明したように、CRC 検出機能は、その入力ベクトル全体のチェックサムを計算します。

CRC アルゴリズムは、バイナリ ベクトルを使用してバイナリ多項式を降べきの順で表します。たとえば、ベクトル [1 1 0 1] は、多項式 x³ + x² + 1 を表します。

メモ

この節で説明する実装は、CRC アルゴリズムの多くの有効な実装の 1 つです。別の実装では、別の数値結果が得られることがあります。

ビットは、最小のインデックス ビットから最大のインデックス ビットに向かって線形フィードバック シフト レジスタ (LFSR) に入力されます。入力メッセージ ビットのシーケンスは、メッセージ多項式の係数を降べきの順で表します。メッセージ ベクトルは r 個の 0 で拡張され、LFSR をフラッシュします (ここで r は生成多項式の次数です)。左端のレジスタ ステージからの出力 d(1) が 1 の場合、シフト レジスタ内のビットは生成多項式の係数と XOR 計算されたものです。拡張されたメッセージ シーケンスが LFSR を介して完全に送信されると、レジスタにはチェックサム [d(1) d(2) . . . d(r)] が含まれます。これはバイナリ長除算の実装です (メッセージ シーケンスが分子で多項式が分母です)。CRC チェックサムは、除算演算の剰余です。

CRC 非直接アルゴリズムの使用例

入力フレームが [1 1 0 0 1 1 0]' で、多項式 M = x⁶ + x⁵ + x² + x に対応し、生成多項式が P = x³ + x² + 1 (次数 r = 3) であるとします。多項式の除算によって、M*x³ = (x⁶ + x³ + x)*P + x となります。剰余は R = x なので、チェックサムは [0 1 0]' です。チェックサムの長さが 3 になるように、左側に 0 が追加されています。

CRC 直接アルゴリズム

ここで、

メッセージ ブロック入力は、$$m_0,m_1,\mathrm{...},m_{k-1}$$

符号語出力は、$$c_0,c_1,\mathrm{...}\text{}\text{},\text{}{c}_{n-1}=\underset{X}{\underbrace{m_0,m_1,\mathrm{...}\text{}\text{},m_{k-1},}}\underset{Y}{\underbrace{d_0,d_1,\mathrm{...},d_{n-k-1}}}$$

直接 CRC 符号化の初期ステップは、位置 X にある 3 つのスイッチによって生起します。このアルゴリズムは k 個のメッセージ ビットを符号化器に送り込みます。これらのビットは、符号語出力の最初の k ビットです。同時に、線形フィードバック シフト レジスタ (LFSR) に k 個のビットが送信されます。k 番目のメッセージ ビットの LFSR への送り込みが完了すると、スイッチは Y の位置に移動します。この例では、LFSR には多項式除算の数値剰余が含まれます。これらのビットは、LFSR からシフトされます。これらのビットは、符号語出力の残りのビット (チェックサム) です。

CRC 符号化の参考文献

[1] Sklar, Bernard., Digital Communications: Fundamentals and Applications, Englewood Cliffs, NJ, Prentice Hall, 1988.

[2] Wicker, Stephen B., Error Control Systems for Digital Communication and Storage, Upper Saddle River, NJ, Prentice Hall, 1995.

ブロック符号

• ブロック符号化機能

• 用語

• ブロック符号化のデータ形式

• モデル内でのブロック符号化器と復号化器の使用

• ブロック符号化の例

• 特定のブロック符号化手法に関するメモ

• 短縮、パンクチャ、および消去

• 整数形式のリード・ソロモン符号

• 生成多項式の決定

• その他のブロック符号タスクの実行

• ブロック符号化の参考文献

ブロック符号化機能

誤り制御符号化の手法では、デジタル通信システムにおいてメッセージが送信されたときに生じる誤りを検出し、可能な場合は訂正します。これを実現するために、符号化器は情報シンボルだけでなく余分な冗長シンボルも送信します。復号化器は受信したものを解釈し、冗長シンボルを使用して、送信中に生じた誤りを検出し、可能な場合は訂正します。送信チャネルにノイズが多い、またはデータがノイズの影響を受けやすい場合、誤り制御符号化を使用する場合があります。データやノイズの性質により、特定のタイプの誤り制御符号化を選択することができます。

ブロック符号化は、誤り制御符号化の特殊なケースです。ブロック符号化手法は、固定数のメッセージ シンボルを固定数の符号シンボルにマッピングします。ブロック符号化器は、データの各ブロックを個別に扱うメモリのないデバイスです。Communications Toolbox には、Simulink ブロック、System object、および MATLAB 関数を使用することによる、ブロック符号化機能が含まれています。

ブロック符号化手法のクラスには、以下の図に示すカテゴリが含まれます。

Communications Toolbox は一般線形ブロック符号をサポートしています。これは、巡回、BCH、ハミング、リード・ソロモン符号 (すべて特殊な線形ブロック符号) も処理します。この製品のブロックは、前述の手法のいずれかを使用して、メッセージを符号化または復号化できます。リード・ソロモン復号化器と BCH 復号化器は復号化中に検出した誤りの数を示します。リード・ソロモン符号化ブロックを使用すると、シンボルまたはビットをデータとして使用するかどうかを決定できます。

メモ

Communications Toolbox のブロックと関数は、2 または 2^m 個のシンボルをもつアルファベットを使用する誤り制御符号用に設計されています。

Communications Toolbox がサポートしている関数.  Communications Toolbox の関数はシミュレーション ブロックの以下の機能をサポートしています。

• 手法の特性 (誤り訂正能力や可能なメッセージ長など) を決定する

• 手法に関連する以下のような下位レベルの計算を実行する

  • 真理表の計算

  • 生成行列またはパリティ チェック行列の計算

  • 生成行列とパリティ チェック行列の間の変換

  • 生成多項式の計算

誤り制御符号化機能の詳細は、ブロック符号を参照してください。

用語

この節では、符号化される情報は "メッセージ" シンボルで構成され、生成される符号は "コードワード" で構成されます。

K メッセージ シンボルの各ブロックは、N メッセージ シンボルで構成されるコードワードに符号化されます。K はメッセージ長と呼ばれ、N はコードワード長と呼ばれ、符号は [N,K] 符号と呼ばれます。

ブロック符号化のデータ形式

各メッセージまたは各コードワードはシンボルを順番に並べたグループです。Block Coding サブライブラリの各ブロックは、次の節バイナリ形式 (すべての符号化方法)で説明するように、タイム ステップごとに 1 ワード処理します。リード・ソロモン符号化ブロックを使用すると、整数形式 (リード・ソロモンのみ)で説明するように、バイナリ データと整数データの間で選択できるようになります。

バイナリ形式 (すべての符号化方法).  メッセージとコードワードをバイナリの "ベクトル" 信号として構築できます。ここで、各ベクトルはメッセージ ワードまたはコードワードを表します。与えられた時間において、符号化器はメッセージ ワード全体を受信してそれを符号化し、コードワード全体を出力します。メッセージ信号と符号信号は同じサンプル時間で動作します。

この例は、時間 0 において、符号化器が 4 ビットのメッセージを受信し、5 ビットのコードワードを生成することを示します。時間 1 では、新しいメッセージに対してこのプロセスを繰り返します。

バイナリ入力を使用するリード・ソロモン "以外の" すべての符号化手法では、必要なメッセージ ベクトルの長さは K で、対応する符号ベクトルの長さは N です。バイナリ入力を使用するリード・ソロモン符号では、符号のシンボルは長さ M の 2 進シーケンスで、ガロア体の要素 GF(2^M) に対応します。この場合、メッセージ ベクトルの長さは M*K で、対応する符号ベクトルの長さは M*N でなければなりません。バイナリ入力の RS Encoder ブロックとバイナリ出力の RS Decoder ブロックは、メッセージとコードワードに対してこの形式を使用します。

ブロック符号化ブロックへの入力がフレームベース ベクトルの場合、入力ベクトルは行ベクトルではなく、列ベクトルでなければなりません。

サンプルベースのメッセージをバイナリ形式で生成するには、Bernoulli Binary Generator ブロックを設定して、その [Probability of a zero] パラメーターが、作成する信号と同じ長さのベクトルになるようにします。フレームベースのメッセージをバイナリ形式で生成するには、同じブロックを設定して、その [Probability of a zero] パラメーターをスカラーにし、その [Samples per frame] パラメーターを作成する信号の長さにします。

シリアル信号の使用

複数のサンプルがまとまってメッセージ ワードまたはコードワードを形成するような状況で、メッセージとコードワードをスカラー信号として構築する場合、Buffer と Unbuffer を使用できます。バッファリングにはレイテンシとマルチレート処理が含まれます。モデルがエラー レートを計算する場合、符号化とバッファリングの組み合わせにおける初期の遅延は Error Rate Calculation ブロックの [Receive delay] パラメーターに影響します。

モデル内の信号のサンプル時間を表示することができます。[デバッグ] タブで、[情報のオーバーレイ] を展開します。[サンプル時間] セクションで、[色] を選択します。または、Probe (Simulink) ブロックを接続線につなげて、サンプル時間、バッファリング、および遅延を評価しやすくすることができます。

整数形式 (リード・ソロモンのみ).  [N,K] リード・ソロモン符号に対するメッセージ ワードは M*K ビットで構成されます。これは 0 から 2^M までの K 個のシンボルを意味します。このシンボルは長さ M の 2 進シーケンスで、降べき順で、ガロア体の要素 GF(2^M) に対応します。リード・ソロモン符号の整数形式を使用すると、メッセージとコードワードを、バイナリ信号ではなく "整数" 信号として構築できます (入力はフレームベースの列ベクトルでなければなりません)。

メモ

この説明で、Simulink は、"最初の" ビットがシンボルの最上位ビットであり、ベクトルの最小インデックスまたはスカラー系列に対する最小時間であることを想定しています。

次の図はリード・ソロモン符号化器におけるバイナリ信号と整数信号の間の等価な関係を示します。復号化器の場合も同様です。

サンプルベースのメッセージを整数形式で生成するには、Random Integer Generator ブロックを設定し、[M-ary number] パラメーターと [Initial seed] パラメーターが目的の長さのベクトルで、[M-ary number] ベクトルのすべてのエントリが 2^M になるようにします。フレームベースのメッセージを整数形式で生成するには、同じブロックを設定して、その [M-ary number] パラメーターと [Initial seed] パラメーターをスカラーにし、その [Samples per frame] パラメーターを作成する信号の長さにします。

モデル内でのブロック符号化器と復号化器の使用

符号化ブロックを設定した後、それらをモデル内に正しく配置するために役立つヒントをいくつか紹介しましょう。

• ブロックに複数の出力がある場合、最初の出力は常に符号化データのストリームです。

  Reed-Solomon ブロックと BCH ブ ロックには 2 番目の出力にエラー カウンターがあります。

• 信号サイズがマスク パラメーターとして適切かどうかを確認してください。たとえば、Binary Cyclic Encoder ブロックを使用し [Message length K] を 4 に設定する場合、入力信号は長さ 4 のベクトルでなければなりません。

  モデル内の信号のサイズを表示することができます。[デバッグ] タブで、[情報のオーバーレイ] を展開します。[信号] セクションで、[信号の次元] を選択します。

ブロック符号化の例

例:整数形式のリード・ソロモン符号.  この例では整数形式のリード・ソロモン符号を使用します。符号化ブロックに対する符号とメッセージ信号の適切なベクトル長を示します。また各コードワードに誤りを発生させる簡単な方法を使用して、誤り訂正を紹介します。

モデルを作成するには、次のブロックを収集し、設定します。

• Random Integer Generator (パラメーター設定を次のように更新):

  • [M-ary number] を 15 に設定します。

  • [Initial seed] を正の数値に設定します。ここでは randn を選択します。

  • [Frame-based outputs] チェック ボックスをオンにします。

  • [Samples per frame] を 5 に設定します。

• Integer-Input RS Encoder (パラメーター設定を次のように更新):

  • [Codeword length N] を 15 に設定します。

  • [Message length K] を 5 に設定します。

• Gain (Simulink) (パラメーター設定を次のように更新):

  • [Gain] を [0; 0; 0; 0; 0; ones(10,1)] に設定します。

• Integer-Output RS Decoder (パラメーター設定を次のように更新):

  • [Codeword length N] を 15 に設定します。

  • [Message length K] を 5 に設定します。

• Simulink Sinks ライブラリの Scope (Simulink)このブロックを 2 つコピーします。

• Simulink Math Operations ライブラリの Add (Simulink)

  • [List of signs] を |-+ に設定します。

前の図に示したようにブロックを接続します。[シミュレーション] タブの [シミュレーション] セクションで、[終了時間] を 500 に設定します。[シミュレーション] セクションは複数のタブに表示されます。

モデル内の信号のベクトル長を表示することができます。[デバッグ] タブで、[情報のオーバーレイ] を展開します。[信号] セクションで、[信号の次元] を選択します。

符号化器は長さ 5 (この場合の K) のベクトルを受け取り、長さ 15 (この場合の N) のベクトルを生成します。復号化器はこの逆を行います。

モデルを実行すると、次のイメージのスコープが生成されます。プロットされる誤りの数は Random Integer Generator ブロック内の [Initial Seed] 値によって異なります。軸の範囲を調整して、1 つ目のスコープとまったく同じにすることができます。2 つ目のスコープ内のプロット領域で右クリックし、[コンフィギュレーション プロパティ] を選択します。[表示] タブで、座標軸の範囲を調整します。

訂正前の誤り数

2 番目のプロットは、復号化器がメッセージの復元中に検出した誤り数です。Gain ブロックが各コードワード内の最初の 5 つのシンボルをゼロで置き換えたため、5 の数がしばしば現れています。しかし、正しいコードワードの最初の 5 個所に 1 つ以上のゼロを含む場合は、誤り数が 5 を超えることはありません。

最初のプロットは元のメッセージと復元されたメッセージとの差で、復号化器が発生したすべての誤りを訂正できたため、プロットの 5 つのデータ ストリームのそれぞれはゼロです。

特定のブロック符号化手法に関するメモ

Block Coding サブライブラリは外観や使い勝手において同じように見えますが、各種の符号化手法は同一ではありません。この節では、このサブライブラリの符号化手法カテゴリ用のパラメーターや信号に適用される、特別なオプションと制限について説明します。以下で説明する符号化手法には、一般線形ブロック符号、巡回符号、ハミング符号、BCH 符号またはリード・ソロモン符号が含まれます。

一般線形ブロック符号

一般線形ブロック符号を使ってメッセージを符号化するには、生成行列が必要です。符号の復号化には、生成行列が必要であり、場合によっては真理表も必要です。Binary Linear Encoder ブロックと Binary Linear Decoder ブロックを使用するには、[Generator matrix] パラメーターと [Error-correction truth table] パラメーターについて理解しなければなりません。

Generator Matrix - [N,K] 線形ブロック符号にメッセージを符号化する処理は、K 行 N 列の生成行列 G によって決定されます。特に、1 行 K 列のメッセージ ベクトル v は、1 行 N 列のコードワード ベクトル vG に符号化されます。G が形式 [I_k, P] または [P, I_k] をもつ場合 (ここで、P は適当な K 行 (N-K) 列の行列で I_k は K 行 K 列の単位行列)、G は "標準形" と呼ばれます。(著者によっては、Clark and Cain[2]のように最初の標準形を使用する場合も、Lin and Costello[3]のように後者を使用する場合もあります)。この製品の線形ブロック符号化ブロックでは、[Generator matrix] のマスク パラメーターが標準形である必要があります。

Decoding Table - 復号化テーブルは、伝送中に生じた符号誤りを訂正する方法を復号化器に示します。ハミング符号は、任意のコードワード内の単一シンボルの誤りを訂正することができます。その他の符号は、指定されたコードワード内の複数のシンボルで発生した誤りを訂正、または部分的に訂正します。

Binary Linear Decoder ブロックを使用すると、[Error-correction truth table] パラメーターで復号化テーブルを指定できます。復号化テーブルは N 列、2^N-K 行の行列で表します。各行は、受信したコードワード ベクトルに対して訂正ベクトルを指定します。

[Error-correction truth table] パラメーターを 0 に設定することで復号化テーブルを明示的に指定することを回避できます。[Error-correction truth table] が 0 の場合、ブロックは関数 syndtable を使用して復号化テーブルを計算します。

巡回符号

巡回符号では、コードワード長 N の形式は 2^M-1 でなければなりません。ここで M は 3 以上の整数です。

Generator Polynomials - 巡回符号は、多項式が符号化過程を完全に決定できるような特殊な代数的性質をもちます。このいわゆる生成多項式は、多項式 x^N-1 の (N-K) 次除算子です。Van Lint の[5]では、生成多項式が巡回符号をどのように決定するかを説明しています。

Binary Cyclic Encoder ブロックと Binary Cyclic Decoder ブロックを使用すると、生成多項式を、そこで K を指定せずに、2 番目のマスク パラメーターとして指定できます。ブロックは、多項式の係数を変数の "昇べき" の順にリストするベクトルを使用して、生成多項式を表します。巡回符号用の生成多項式は、関数 cyclpoly を使用して見つけることができます。

生成多項式を指定しない場合、2 番目のマスク パラメーターを K の値に設定します。

ハミング符号

ハミング符号では、コードワード長 N の形式は 2^M-1 でなければなりません。ここで M は 3 以上の整数です。メッセージ長 K は N-M に等しくなければなりません。

Primitive Polynomials - ハミング符号は 2^M 個の要素 (より一般的には、素数 p に対して p^M 個の要素) をもつ代数体に依存します。そのようなフィールドの要素は、"原始元" と呼ばれる体の特定の要素に "相対的な" 名前が付けられます。原始元の最小多項式は "原始多項式" と呼ばれます。Hamming Encoder ブロックと Hamming Decoder ブロックを使用すると、計算に使用する有限体用の原始多項式を指定できます。この多項式を指定する場合は、2 番目のマスク パラメーター フィールドで指定します。ブロックは、多項式の係数を変数の "昇べき" の順にリストするベクトルを使用して原始多項式を表します。ガロア体用の生成多項式は、関数 gfprimfd を使用して見つけることができます。

原始多項式を指定しない場合、2 番目のマスク パラメーターを K の値に設定します。

BCH 符号

BCH 符号は、有限体を使用して構築される巡回誤り修正符号です。これらの符号では、コードワード長 N の形式は 2^M-1 でなければなりません。ここで M は 3 から 9 までの整数です。メッセージ長 K は N に依存する特定の値に制限されます。与えられた N に対する有効な K の値については、comm.BCHEncoder System object™ のリファレンス ページを参照してください。BCH 符号に関するコードワード長、メッセージ長、および誤り訂正能力間の関係を説明する既知の解析式はありません。

狭義の BCH 符号

狭義の生成多項式は LCM[m_1(x), m_2(x), ..., m_2t(x)] です。ここで各項は以下のとおりです。

• LCM は最小公倍数を表します。

• m_i(x) は αⁱ に対する最小多項式を表します。α は体 GF(n+1) の既定の原始多項式の根です。

• t は符号の誤り訂正能力を表します。

リード・ソロモン符号

リード・ソロモン符号はバースト発生する誤りの訂正に便利です。単純なケースでは、リード・ソロモン符号のコードワードの長さは形式 N= 2^M-1 でなければなりません。ここで 2^M は符号のシンボル数です。リード・ソロモン符号の誤り訂正能力は floor((N-K)/2) です。ここで K はメッセージ ワードの長さです。N-K は偶数でなければなりません。

N が 2^M-1 よりも小さい、短縮リード・ソロモン符号を使用すると便利な場合があります。この場合、符号化器は 2^M-1-N 個のゼロのシンボルを各メッセージ ワードとコードワードに追加します。短縮リード・ソロモン符号の誤り訂正能力も floor((N-K)/2) になります。Communications Toolbox の Reed-Solomon ブロックは短縮リード・ソロモン符号を実装することができます。

Effect of Nonbinary Symbols - リード・ソロモン符号と、この製品でサポートされている他の符号との違いの 1 つは、リード・ソロモン符号はシンボルを GF(2) ではなく、GF(2^M) で処理することです。各シンボルは M ビットで指定されます。リード・ソロモン符号のシンボルの非 0-1 的な性質により、Reed-Solomon ブロックは他の符号化ブロックと以下の点で異なります。

• Integer-Input RS Encoder ブロックと Integer-Output RS Decoder ブロックを介して、整数形式を使用できます。

• バイナリ形式では、ベクトル長が、メッセージに対しては M*K (K ではない) の整数倍、コードワードに対しては同じ整数 M*N (N ではない) であることを想定しています。

Error Information - リード・ソロモンの復号化ブロック (Binary-Output RS Decoder と Integer-Output RS Decoder) はシミュレーション中に誤りに関する情報を返します。2 番目の出力信号は、そのブロックが入力コードワード内で検出した誤り数を示します。2 番目の出力の A -1 は、ブロックが、その符号化方式で訂正可能な数を上回る誤りを検出したことを示します。

短縮、パンクチャ、および消去

多くの標準がパンクチャド符号を利用し、デジタル受信機は容易に消去を出力できます。受信機が消去を生成するフェージング チャネルでは、BCH と RS のパフォーマンスが大幅に改善されます。

"パンクチャドコードワード" ではパリティ シンボルだけが削除され、"短縮コードワード" では情報シンボルだけが削除されます。コードワードは、情報シンボルまたはパリティ シンボルのいずれかにこれらの消去をもつことができます。

短縮、パンクチャ、および消去を使用するリード・ソロモンの例

このセクションでは、短縮、パンクチャ、および消去を使用した代表的なリード・ソロモン符号化例を、ますます複雑になる誤り訂正を含めて作成します。

短縮とパンクチャを使用した符号化器例

次の図は、短縮とパンクチャを使用した (7,3) リード・ソロモン符号化器の代表的な例を示しています。

この図では、メッセージ ソースにより I₁I₂ で指定される 2 つの情報シンボルが出力されます (BCH の例では、シンボルはバイナリ ビットです)。この符号は短縮 (7,3) 符号であるため、情報シンボルの前にゼロを追加しなければなりません。これにより、0I₁I₂ という 3 つのシンボルから構成されるメッセージが生成されます。変更されたメッセージ シーケンスは、RS で符号化され、追加された情報ゼロはそのあと削除されます。その結果 I₁I₂P₁P₂P₃P₄ が生成されます (この例では、パリティ ビットはコードワードの末尾にあります)。

パンクチャ操作は、パンクチャ ベクトルによって制御されます。ここでは、このパンクチャ ベクトルは 1011 です。パンクチャ ベクトル内では、1 はシンボルが保持され、0 はシンボルが破棄されたことを意味します。この例では、パンクチャ操作により 2 番目のパリティ シンボルが削除され、I₁I₂P₁P₃P₄ という最終的なベクトルが生成されます。

短縮とパンクチャを使用した復号化器例

次の図は、短縮コードワードおよびパンクチャドコードワードでの RS 復号化器の動作を示しています。

このケースは、短縮とパンクチャを使用した RS 符号化器の図に示した符号化器の動作に対応します。前の図に示したとおり、符号化器は (5,2) コードワードを受信します。これは (7,3) コードワードから 1 シンボル短縮され、さらにその 1 シンボルはパンクチャされているためです。

最初のステップとして、復号化器は、コードワードの第 2 のパリティ位置に E で指定された消去を追加します。これは、パンクチャ ベクトル 1011 に対応します。前の図に示したとおり、ゼロを追加することは短縮を意味します。1 回の消去は、4 つの消去を訂正できる符号の消去訂正機能を超えません。復号化操作により、3 つのシンボルで構成されるメッセージ DI₁I₂ が生成されます。前の図のように最初のシンボルは切り捨てられるので、最終出力は I₁I₂ になります。

短縮、パンクチャ、消去を使用する復号化器の例

次の図は、パンクチャされ、短縮コードワードに対して動作しながら、受信機によって生成された消去を生成する復号化器の様子を示しています。

この図では、復調器は符号化器が送信した I₁I₂P₁P₃P₄ ベクトルを受信します。復調器は、受信した 5 つのシンボルのうち 2 つは、信頼できないので消去されることを宣言するため、シンボル 2 と 5 は消去と見なされます。外部ソースによって提供された 01001 ベクトルは、これらの消去を示しています。消去ベクトル内では、1 はシンボルが消去シンボルで置き換えられること、0 はシンボルが変更なしで渡されることを意味します。

復号化器のブロックは、コードワードと消去ベクトルを受信し、ベクトル 01001 で示される消去を実行します。消去ベクトル内では、1 はシンボルが消去シンボルで置き換えられること、0 はシンボルが変更なしで渡されることを意味します。結果のコードワード ベクトルは、I₁EP₁P₃E になります。ここで、E は消去シンボルです。

コードワードは、符号化操作で使用したパンクチャ ベクトル (1011 など) に基づきデパンクチャされます。したがって、消去シンボルが P₁ と P₃ の間に挿入され、I₁EP₁EP₃E というコードワード ベクトルが生成されます。

復号化の直前に、情報ベクトルの冒頭にゼロを追加することは短縮を意味します。結果のベクトルは、0I₁EP₁EP₃E になるため、(7,3) コードワードは Berlekamp アルゴリズムに送られます。

このコードワードは復号化され、3 つのシンボルで構成される DI₁I₂ (ここで、D はダミー シンボルを示します) というメッセージが生成されます。最後に、メッセージ ベクトルから D シンボルを削除することは、短縮を意味し、元の I₁I₂ ベクトルが生成されます。

詳細については、消失、パンクチャ、および短縮を使用したリード・ソロモン符号化 MATLAB の例またはSimulink での消失、パンクチャ、および短縮を使用したリード・ソロモン符号化の例を参照してください。

整数形式のリード・ソロモン符号

整数形式のリード ソロモン符号を使用するモデルについては、例:整数形式のリード・ソロモン符号を参照してください。

生成多項式の決定

巡回、BCH、リード・ソロモン符号に対する生成多項式を求めるには、それぞれ関数 cyclpoly、bchgenpoly、または rsgenpoly を使用します。次のコマンドを見てみましょう。

genpolyCyclic = cyclpoly(15,5) % 1+X^5+X^10
genpolyBCH = bchgenpoly(15,5)  % x^10+x^8+x^5+x^4+x^2+x+1
genpolyRS = rsgenpoly(15,5)

これらのコマンドは、異なるタイプのブロック符号に対する生成多項式を求めます。出力は以下のようになります。

genpolyCyclic =

     1     0     0     0     0     1     0     0     0     0     1


genpolyBCH = GF(2) array.

Array elements =

     1     0     1     0     0     1     1     0     1     1     1


genpolyRS = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)

Array elements =

     1     4     8    10    12     9     4     2    12     2     7

これらの出力の形式は、次のように変わります。

• cyclpoly は、多項式の係数を変数の "昇べき" の順にリストする整数の行ベクトルを使用して、生成多項式を表します。

• bchgenpoly と rsgenpoly は、多項式の係数を変数の "降べき" の順にリストするガロア行ベクトルを使用して、生成多項式を表します。

• rsgenpoly は、二元体 GF(2) 以外のガロア体の係数を使用します。これらの係数の意味の詳細は、整数をガロア体にどのように対応づけるかとガロア体上の多項式を参照してください。

生成多項式の非一意性

メッセージ長とコードワード長のペアによって、生成多項式が一意に決定されない場合があります。上記の例の関数の構文には、指定する特定の制約を満たす生成多項式を取り出すためのオプションも含まれています。構文のオプションの詳細は、関数のリファレンス ページを参照してください。

生成多項式の代数表現

bchgenpoly と rsgenpoly によって生成される生成多項式の形式は、(X - A^b)(X - A^b+1)...(X - A^b+2t-1) です。ここで、A は適切なガロア体に対する原始元で、b と t は整数です。この式の詳細は、関数のリファレンス ページを参照してください。

その他のブロック符号タスクの実行

この節では、線形ブロック符号に関連する典型的なパラメーターを計算する関数と、別の形式に情報を変換する関数について説明します。

• 線形ブロック符号の誤り訂正と誤り検出

  線形ブロック符号を使用して、d_min -1 件の誤り検出か t = $$\left[\frac{1}{2}(d_{\min }-1)\right]$$ 件の誤り訂正を行うことができます。

  符号の誤り訂正能力を低くすることで、t 件よりも多くの誤りを検出できます。たとえば、d_min = 7 の符号では、t = 3 件の誤りを訂正できますが、代わりに最大 4 件の誤り検出と 2 件の誤り訂正を行うこともできます。

• 誤り訂正能力を求める

  関数 bchgenpoly および rsgenpoly は、BCH またはリード・ソロモン符号の誤り訂正能力を示すオプションの第 2 出力引数を返すことができます。たとえば、次のコマンドを例に考えてみます。

  [g,t] = bchgenpoly(31,16);
  t
  t =
  
       3
  

  これらのコマンドにより、[31, 16] BCH 符号は各コードワード内の 3 つの誤りまで訂正できることがわかます。

• 生成行列とパリティ チェック行列を求める

  コードワード長が 2^m-1 のハミング符号に対するパリティ チェック行列と生成行列を求めるには、以下に示すように関数 hammgen を使用します。m は、少なくとも 3 でなければなりません。

  [parmat,genmat] = hammgen(m); % Hamming
  

  巡回符号に対するパリティ チェック行列と生成行列を求めるには、関数 cyclgen を使用します。コードワード長と有効な生成多項式を与えなければなりません。コードワード長とメッセージ長を指定した後、関数 cyclpoly を使用して有効な生成多項式を生成することができます。次に例を示します。

  [parmat,genmat] = cyclgen(7,cyclpoly(7,4)); % Cyclic

• パリティ チェック行列と生成行列の変換

  関数 gen2par は、生成行列からパリティ チェック行列への変換、およびその逆の変換を行います。gen2par のリファレンス ページに、これを示す例があります。

ブロック符号化の参考文献

[1] Berlekamp, Elwyn R., Algebraic Coding Theory, New York, McGraw-Hill, 1968.

[2] Clark, George C. Jr., and J. Bibb Cain, Error-Correction Coding for Digital Communications, New York, Plenum Press, 1981.

[3] Lin, Shu, and Daniel J. Costello, Jr., Error Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ, Prentice-Hall, 1983.

[4] Peterson, W. Wesley, and E. J. Weldon, Jr., Error-Correcting Codes, 2nd ed., Cambridge, MA, MIT Press, 1972.

[5] van Lint, J. H., Introduction to Coding Theory, New York, Springer-Verlag, 1982.

[6] Wicker, Stephen B., Error Control Systems for Digital Communication and Storage, Upper Saddle River, NJ, Prentice Hall, 1995.

[7] Gallager, Robert G., Low-Density Parity-Check Codes, Cambridge, MA, MIT Press, 1963.

[8] Ryan, William E., “An introduction to LDPC codes,” Coding and Signal Processing for Magnetic Recoding Systems (Vasic, B., ed.), CRC Press, 2004.

畳み込み符号

• 畳み込み符号の機能

• 畳み込み符号の多項式表現

• 畳み込み符号のトレリス表現

• 畳み込み符号の作成と復号化

• MATLAB を使用した符号化率 -2/3 のフィードフォワード符号化器の設計

• Simulink を使用した符号化率 2/3 のフィードフォワード符号化器の設計

• MATLAB を使用した畳み込み符号のパンクチャ

• Simulink を使用したフィードバックをもつ組織符号化器の実装

• 軟判定復号化

• フィードバック符号化器を使用したテールバイト符号化

• 畳み込み符号化の参考文献

畳み込み符号の機能

畳み込み符号化は、誤り制御符号化の特殊な場合です。ブロック符号化器と異なり、畳み込み符号化器はメモリのないデバイスではありません。畳み込み符号化器は固定数のメッセージ シンボルを受け取り、固定数のコード シンボルを生成しますが、計算は入力シンボルの現在のセットのみでなく、前の入力シンボルの一部にも依存します。

Communications Toolbox は Simulink ブロック、System object、および MATLAB 関数で畳み込み符号化機能を提供します。この製品は、トレリス構造体または一連の生成多項式で記述されるフィードフォワードまたはフィードバック畳み込み符号をサポートします。硬判定と軟判定の復号化を実装するために、ビタビ アルゴリズムを使います。

製品には "事後" 確率復号化器も含まれます。これは畳み込み符号の軟出力復号化に使用できます。

畳み込み符号化に関する背景情報は、畳み込み符号化の参考文献の文献を参照してください。

畳み込み符号化用ブロック パラメーター

畳み込み符号を処理するには、Convolutional サブライブラリの Convolutional Encoder ブロック、Viterbi Decoder ブロック、および/または APP Decoder ブロックを使用します。符号化器と復号化器の両方でマスク パラメーターが必要な場合は、両方のブロックで同じ値を使用します。

Convolutional サブライブラリのブロックは、畳み込み符号化器の 2 つの異なる表現のいずれかが使用されると仮定しています。

• シフト レジスタと剰余 2 加算器のブロック線図を使用して符号化器を設計する場合、符号生成多項式行列を計算し、その結果として (Communications Toolbox の) 関数 poly2trellis を使用して、自動的にトレリス構造体マスク パラメーターを生成できます。例については、Simulink を使用した符号化率 2/3 のフィードフォワード符号化器の設計 を参照してください。

• トレリス ダイアグラムを使用して符号化器を設計する場合 MATLAB でトレリス構造体を構築し、それをマスク パラメーターとして使用できます。

これらの表現の詳細については、畳み込み符号の多項式表現および畳み込み符号のトレリス表現を参照してください。

ブロックでの多項式表現の使用

Convolutional Encoder ブロック、Viterbi Decoder ブロック、または APP Decoder ブロックで多項式表現を使用するには、Communications Toolbox のユーティリティ関数 poly2trellis を使用します。この関数は多項式表現を受け取り、それをトレリス表現に変換します。たとえば次のコマンドは、拘束長が 5 で、生成多項式が 35 と 31 の符号化器のトレリス表現を計算します。

trellis = poly2trellis(5,[35 31]);

畳み込み符号化ブロックの 1 つとともにこの符号化器を使用するには、次のような poly2trellis コマンドを

poly2trellis(5,[35 31]);

[Trellis structure] パラメーター フィールドに配置します。

畳み込み符号の多項式表現

畳み込み符号化器の多項式表現は、シフト レジスタと剰余 2 加算器の間の接続を記述します。たとえば、下図は、1 つの入力、2 つの出力、2 つのシフト レジスタをもつフィードフォワード畳み込み符号化器を示しています。

畳み込み符号化器の多項式表現は、符号化器がフィードフォワードか、フィードバックかに応じて、2 つまたは 3 つの成分をもちます。

• 拘束長

• 生成多項式

• フィードバック接続多項式 (フィードバック符号化器のみ)

拘束長.  符号化器の拘束長は、長さが符号化器ダイアグラムの入力数であるベクトルを形成します。このベクトルの要素は、現在の入力ビットを含む各シフト レジスタに格納されたビット数を示します。

上記の図で、拘束長は 3 です。符号化器は 1 入力ストリームをもつため、拘束長はスカラー値です。その値は、入力に対するシフト レジスタ数プラス 1 です。

生成多項式.  符号化器ダイアグラムが k 入力と n 出力をもつ場合、符号生成行列は k 行 n 列行列です。i 行 j 列の要素は、i 番目の入力が j 番目の出力にどのように寄与するかを示します。

組織的なフィードバック符号化器の "組織的な" ビットに対して、符号生成行列のエントリと対応するフィードバック接続ベクトルの要素を一致させます。詳細は、下記のフィードバック接続多項式を参照してください。

その他の状況では、以下のように行列内の (i,j) エントリを決定することができます。

1. シフト レジスタからの接続線が加算器に接続される各点に 1 を置き、それ以外の点に 0 を置くことにより、2 進数表現を作成します。2 進数表現の最も左の点は現在の入力を表し、最も右の点はシフト レジスタに残っている最も古い入力を表します。

2. この 2 進数表現を、最も右のビットから開始される連続する 3 つのビットの組と考えることで、8 進数表現に変換します。各 3 ビット内の最も右のビットは、最下位のビットです。ビット数が 3 の倍数でない場合、必要に応じて左端にゼロビットを置きます (たとえば、1101010 を 001 101 010 と解釈して 152 に変換します)。

たとえば、上記の図の上部および下部の加算器に対応する 2 進数は、それぞれ 110 と 111 です。これらの 2 進数は、それぞれ、8 進数の 6 と 7 に等しいので、生成多項式行列は [6 7] です。

メモ

str2num(dec2base(bin2dec('110'),8)) のようなコードを使用して MATLAB で 2 進数から 8 進数への変換を行うことができます。

有効な畳み込み符号生成器の表として、セクションブロック符号化の参考文献の[2]、特に文献の付録を参照してください。

フィードバック接続多項式.  フィードバック符号化器を表している場合は、フィードバック接続多項式のベクトルが必要です。このベクトルの長さは、符号化器ダイアグラムの入力数です。このベクトルの要素は、8 進法を使って各入力に対するフィードバック接続を示します。最初に上記のステップ 1 のように 2 進数表現を作成します。その後、2 進数表現を上記のステップ 2 のように 8 進数表現に変換します。

符号化器がフィードバック設定をもち、組織的である場合は、符号生成器と組織的なビットに対応するフィードバック接続パラメーターは、同じ値をもたなければなりません。

符号化率 1/2 のフィードバック畳み込み符号化器のトレリス構造体の使用

次の図に表示されているフィードバックを使用して、符号化率 1/2 の組織畳み込み符号化器を表すトレリス構造体を作成します。

この符号化器は、拘束長が 5 で、生成多項式行列が [37 33] で、フィードバック接続多項式は 37 です。

最初の生成多項式は 8 進数 37 です。2 番目の生成多項式は 8 進数 33 です。フィードバック多項式は 8 進数 37 です。最初の出力は組織的なビットに対応するため、最初の生成多項式はフィードバック接続多項式と一致します。

バイナリ ベクトル [1 1 1 1 1] は 8 進数 37 を表し、図の上列の 2 進数値に対応します。バイナリ ベクトル [1 1 0 1 1] は 8 進数 33 を表し、図の下列の 2 進数値に対応します。これらの 2 進数値は、図におけるレジスタの出力から 2 つの加算器への接続を示します。最初の 1 は入力ビットに対応します。

関数 poly2trellis を使用して多項式をトレリス構造体に変換します。フィードバック多項式と共に使用すると、poly2trellis はトレリスの入力へのフィードバック接続を作成します。

trellis = poly2trellis(5,[37 33],37)

trellis = struct with fields:
     numInputSymbols: 2
    numOutputSymbols: 4
           numStates: 16
          nextStates: [16x2 double]
             outputs: [16x2 double]

ランダムなバイナリ データを生成します。指定したトレリス構造体を使用してデータを畳み込み符号化します。トレリス構造体、トレースバック長 34、打ち切り操作モード、硬判定を指定したビタビ アルゴリズムを使用して、符号化したデータを復号化します。

data = randi([0 1],70,1);
codedData = convenc(data,trellis);
tbdepth = 34; % Traceback depth for Viterbi decoder
decodedData = vitdec(codedData,trellis,tbdepth,'trunc','hard');

復号化されたデータにビット誤りがないことを確認します。

biterr(data,decodedData)

ans = 0

MATLAB での多項式表現の使用.  関数 convenc および vitdec で多項式表現を使用するには、最初に関数 poly2trellis を使用してトレリス表現に変換します。たとえば、以下のコマンドは、畳み込み符号の多項式表現の節に示された符号化器のトレリス表現を計算します。

trellis = poly2trellis(3,[6 7]);

MATLAB 構造体 trellis は、convenc および vitdec に対する適切な入力引数です。

畳み込み符号のトレリス表現

畳み込み符号化器のトレリス表現は、符号化器への入力が符号化器の出力と状態遷移にどのように影響を与えるかを示します。この節では、トレリスについて説明し MATLAB でトレリスを表現する方法と、MATLAB トレリスの例を示します。

下図は、前節の畳み込み符号化器に対するトレリスを示しています。符号化器は、4 つの状態 (2 進数で 00 から 11 まで番号付け)、1 ビット入力、および 2 ビット出力をもちます (出力ビットに対する入力ビットの比は、この符号化器を符号化率 -1/2 の符号化器にします)。実線矢印は、現在の入力がゼロであるときに符号化器の状態がどのように変化するかを示し、点線の矢印は、現在の入力が 1 であるときに符号化器の状態がどのように変化するかを示します。各矢印の上の 8 進数は、符号化器の現在の出力を示します。

このトレリス ダイアグラムの解釈の例として、符号化器の状態が 10 で、ゼロ入力を受信する場合、コード シンボル 3 を出力し、状態 01 に変化します。状態 10 で入力 1 を受信する場合は、コード シンボル 0 を出力し、状態 11 に変化します。

トレリスには対応する多項式表現をもたないものがありますが、畳み込み符号化器の多項式表現はトレリス表現と等価です。

MATLAB でのトレリスの指定.  MATLAB でトレリスを指定するには、トレリス構造体と呼ばれる特殊な MATLAB の構造体形式を使います。トレリス構造体は、次の表のように 5 個のフィールドをもたなければなりません。

符号化率 k/n の符号に対するトレリス構造体のフィールド

トレリス構造体のフィールド	次元	平均
numInputSymbols	スカラー	符号化器への入力シンボルの数: 2k
numOutputsymbols	スカラー	符号化器からの出力シンボルの数: 2n
numStates	スカラー	符号化器内の状態の数
nextStates	numStates 行 2k 列の行列	現在の状態と現在の入力のすべての組み合わせの次の状態
outputs	numStates 行 2k 列の行列	現在の状態と現在の入力のすべての組み合わせの出力 (8 進数)

メモ

トレリス構造体は任意の名前でかまいませんが、フィールドは表に示してある通りの "正確な" 名前でなければなりません。フィールド名は、大文字と小文字を区別します。

nextStates 行列において、各エントリは、0 ～ numStates-1 の間の整数です。開始状態が i-1 で入力ビットが 10 進数表現 j-1 である場合、i 行 j 列の要素が次の状態を示します。入力ビットを 10 進数に変換するには、最初の入力ビットを最上位ビット (MSB) として使用します。たとえば、nextStates 行列の 2 列目は、現在の入力値のセットが {0,...,0,1} であるときに、次の状態を保存します。状態に数値を割り当てる方法の詳細は、istrellis のリファレンス ページを参照してください。

outputs 行列では、開始状態が i-1 で入力ビットが 10 進数表現 j-1 である場合、i 行 j 列の要素が符号化器の出力を示します。10 進数値に変換するには、最初の出力ビットを MSB として使用します。

MATLAB トレリス構造体の作成法.  各フィールドに置きたい情報についてわかると、以下の方法によってトレリス構造体を作成することができます。

• structurename.fieldname 表記を使って、5 個のフィールドを個別に定義します。たとえば、s という構造体の最初のフィールドは、以下のコマンドを使って設定します。その他のフィールドを定義するには、さらにコマンドを使います。

  s.numInputSymbols = 2;
  

  このアプローチの詳細は、関数 istrellis のリファレンス ページを参照してください。

• すべてのフィールド名およびそれらの値を 1 つの struct コマンドに収集します。次に例を示します。

  s = struct('numInputSymbols',2,'numOutputSymbols',2,...
     'numStates',2,'nextStates',[0 1;0 1],'outputs',[0 0;1 1]);
  

• 符号化器の多項式表現から開始し、関数 poly2trellis を使って有効なトレリス構造体に変換します。詳細については、畳み込み符号の多項式表現を参照してください。

構造体が有効なトレリス構造体であるかどうかを調べるには、関数 istrellis を使用します。

例:MATLAB トレリス構造体.  以下のトレリスを考えます。

これを記述するトレリス構造体を作成するには、以下のコマンドを使います。

trellis = struct('numInputSymbols',2,'numOutputSymbols',4,...
'numStates',4,'nextStates',[0 2;0 2;1 3;1 3],...
'outputs',[0 3;1 2;3 0;2 1]);

トレリス ダイアグラムが実線の矢印と点線の矢印の 2 種類の入力パスをもつので、入力シンボル数は 2 です。矢印の上の数値は 0、1、2、3 のいずれかなので、出力シンボルの数は 4 です。トレリス ダイアグラムの左側に 4 つの点があるため、状態数は 4 です (右側にも同じく 4 つあります)。次の状態の行列を計算するために、行がトレリスの左側の 4 つの現在の状態に対応し、列が 0 と 1 の入力に対応し、要素がトレリスの右側の矢印の先端で次の状態を与える行列を作成します。出力の行列を計算するために、行と列が次の状態の行列であり、要素がトレリス内の矢印の上に示される 8 進数の出力を与える行列を作成します。

畳み込み符号の作成と復号化

畳み込み符号を符号化および復号化するための関数は、convenc と vitdec です。この節では、これらの関数を使った畳み込み符号の作成と復号化について説明します。

符号化.  畳み込み符号を作成するための convenc の簡単な使用法を以下のコマンドに示します。

% Define a trellis.
t = poly2trellis([4 3],[4 5 17;7 4 2]);
% Encode a vector of ones.
x = ones(100,1);
code = convenc(x,t);

最初のコマンドは、フィードフォワード畳み込み符号化器の多項式表現を、対応するトレリス表現に変換します。2 番目のコマンドは、100 ビットまたは 50 個の 2 ビット シンボルを符号化します。この例の符号化率は 2/3 なので、出力ベクトル code には 150 ビット (100 入力ビットの 3/2 倍) が含まれます。

トレリスが異常な畳み込み符号に対応するかどうかをチェックするには、関数 iscatastrophic を使用します。

硬判定復号化.  硬判定を使用して復号化するには、フラグ 'hard' と "2 進数" 入力データと共に関数 vitdec を使用します。convenc の出力は 2 進数なので、硬判定復号化は、追加処理なしで convenc の出力を直接使用することができます。この例は、前の例を拡張したもので、硬判定復号化を実装しています。

Define a trellis.

t = poly2trellis([4 3],[4 5 17;7 4 2]);
Encode a vector of ones.

code = convenc(ones(100,1),t);
Set the traceback length for decoding and decode using vitdec.

tb = 2;
decoded = vitdec(code,t,tb,'trunc','hard');
Verify that the decoded data is a vector of 100 ones.

isequal(decoded,ones(100,1))

ans = logical
   1

軟判定復号化.  軟判定を使用して復号化するには、フラグ 'soft' と共に関数 vitdec を使用します。軟判定ビットの数 (nsdec) を指定し、0 から 2^nsdec-1 までの整数で構成される入力データを使用します。

入力 0 は最も信頼性の高い 0 を表し、入力 2^nsdec-1 は最も信頼性の高い 1 を表します。その他の値は、比較的信頼性の低い判定を表します。たとえば、次の表は、3 ビット軟判定に対する値の解釈をまとめています。

3 ビット軟判定に対する入力値

入力値	解釈
0	最も信頼性の高い 0
1	2 番目に信頼性の高い 0
2	3 番目に信頼性の高い 0
3	最も信頼性の低い 0
4	最も信頼性の低い 1
5	3 番目に信頼性の高い 1
6	2 番目に信頼性の高い 1
7	最も信頼性の高い 1

MATLAB を使用した軟判定復号化の実装

次のスクリプトは、3 ビット軟判定での復号化を説明しています。最初に convenc を使用して畳み込み符号を作成し、awgn を使用して符号にホワイト ガウス ノイズを追加します。その後、軟判定復号化を準備するため、例では quantiz を使用してノイズを含むデータ値を 0 から 7 までの整数の適切な判定値にマッピングします。quantiz の 2 番目の引数は、どのデータ値が 0、1、2 などにマッピングされるかを決定する分割ベクトルです。分割は、0 に近い値が 0 にマッピングされ、1 に近い値が 7 にマッピングされるように選択されます (アプリケーションで必要な場合は、分割を調整して復号化パフォーマンスを高めることができます)。最後に、例では符号を復号化し、ビット エラー レートを計算します。復号化されたデータと元のメッセージの比較時に、例では復号化の遅延を考慮に入れなければなりません。vitdec の連続操作モードではトレースバック長と等しい遅延が生じるので、msg(1) は decoded(1) ではなく decoded(tblen+1) に対応します。

s = RandStream.create('mt19937ar', 'seed',94384);
prevStream = RandStream.setGlobalStream(s);
msg = randi([0 1],4000,1); % Random data
t = poly2trellis(7,[171 133]); % Define trellis.
% Create a ConvolutionalEncoder System object
hConvEnc = comm.ConvolutionalEncoder(t);
% Create an AWGNChannel System object.
hChan = comm.AWGNChannel('NoiseMethod', 'Signal to noise ratio (SNR)',...
  'SNR', 6);
% Create a ViterbiDecoder System object
hVitDec = comm.ViterbiDecoder(t, 'InputFormat', 'Soft', ...
    'SoftInputWordLength', 3, 'TracebackDepth', 48, ...
    'TerminationMethod', 'Continuous');
% Create a ErrorRate Calculator System object. Account for the receive
% delay caused by the traceback length of the viterbi decoder.
hErrorCalc = comm.ErrorRate('ReceiveDelay', 48);
ber = zeros(3,1); % Store BER values
code = step(hConvEnc,msg); % Encode the data.
hChan.SignalPower = (code'*code)/length(code);
ncode = step(hChan,code); % Add noise.

% Quantize to prepare for soft-decision decoding.
qcode = quantiz(ncode,[0.001,.1,.3,.5,.7,.9,.999]);

tblen = 48; delay = tblen; % Traceback length
decoded = step(hVitDec,qcode); % Decode.

% Compute bit error rate.
ber = step(hErrorCalc, msg, decoded);
ratio = ber(1)
number = ber(2)
RandStream.setGlobalStream(prevStream);

出力は以下のようになります。

number =

     5


ratio =

    0.0013

Simulink を使用した軟判定復号化の実装.  この例では、シミュレーションの概要で説明されているモデルを使用して、符号化率 1/2 の畳み込み符号を作成します。軟判定を実行するために、量子化と Viterbi Decoder ブロックを使用します。

畳み込み符号の定義

この例のフィードフォワード畳み込み符号化器を以下に示します。

符号化器は 1 つの入力をもつので、符号化器の拘束長はスカラーです。拘束長の値は、シフト レジスタに格納されたビット数です。これには現在の入力も含まれます。6 つのメモリ レジスタがあり、現在の入力は 1 ビットです。したがって、符号の拘束長は 7 になります。

符号化器は 1 つの入力と 2 つの出力をもつので、符号生成器は 8 進数の 1 行 2 列の行列です。行列内の最初の要素は、最初の出力に関連する入力値を示し、2 番目の要素は、2 番目の出力に関連する入力値を示します。

たとえば、符号化器ダイアグラムの最初の出力は、ダイアグラムの入力値の配列の右端の要素および左端の 4 つの要素の剰余 2 の和です。7 桁の 2 進数 1111001 はこの情報を取得しますが、これは 8 進数の 171 と等価です。したがって、8 進数 171 は、符号生成行列の最初のエントリとなります。ここでは、各 3 桁ビットで最上位ビットとして左端のビットを使用します。2 番目の出力は、2 進数 1011011 に対応します。これは、8 進数 133 に相当します。したがって、符号生成器は [171 133] になります。

Convolutional Encoder ブロックの [Trellis structure] パラメーターは、データ処理にどの符号を使用するかを伝えます。この場合、Communications Toolbox の関数 poly2trellis は、拘束長と 8 進数の組を有効なトレリス構造体に変換します。

Convolutional Encoder ブロックに入るときのメッセージ データはスカラー ビット ストリームですが、ブロックから出てくる符号化済みのデータは、長さ 2 のバイナリ ベクトルのストリームです。

受信データのマッピング

受信データ、すなわち AWGN Channel ブロックの出力は、-1 および 1 に近い複素数で構成されます。元のバイナリ メッセージを再構築するためには、モデルの受信機部分で畳み込み符号を復号化しなければなりません。このモデルの Viterbi Decoder ブロックでは、入力データが 0 ～ 7 の整数であると想定しています。このモデルのカスタム サブシステムである復調器は、受信データを Viterbi Decoder ブロックが正しく解釈できる形式に変換します。具体的には、復調器サブシステムは以下を行います。

• 虚数部を削除することで、受信データ信号を実信号に変換します。送信されたデータの虚数部はゼロ (小さな丸め誤差は無視) であること、およびチャネル ノイズはあまり強くないことなどの理由で、受信データの虚数部には必須の情報が含まれていないと仮定できます。

• ノイズの推定値の標準偏差で除算し、-1 で乗算することにより、受信データを正規化します。

• 3 つのビットを使用して正規化データを量子化します。

このマッピングと Viterbi Decoder ブロックの判定マッピングの組み合わせにより、このモデルの送信側で BPSK Modulator Baseband ブロックが実行する BPSK 変調が逆になります。復調器サブシステムを詳しく調べるには、[Soft-Output BPSK Demodulator] というラベルのアイコンをダブルクリックします。

畳み込み符号の復号化

受信データが 3 ビットの判定値をもつ長さ 2 のベクトルに正しくマッピングされると、Viterbi Decoder ブロックによりそれが復号化されます。[Decision type] パラメーターは [Soft Decision] で、[Number of soft decision bits] パラメーターは 3 であるため、ブロックは 2³ の異なる入力値をもつ軟判定アルゴリズムを使用します。

データの軟判定解釈

[Decision type] パラメーターが [Soft Decision] に設定されると、Viterbi Decoder ブロックでは 0 ～ 2^b-1 の入力値が要求されます。ここで、b は [Number of soft decision bits] パラメーターです。ブロックは、0 を、コードワード ビットが 0 であるという最も信頼性の高い判定であると解釈し、2^b-1 を、コードワード ビットが 1 であるという最も信頼性の高い判定であると解釈します。これらの極値の間の値は、それらよりも信頼性の低い判定を表します。次の表は、この例の入力値として使用できる 8 つの値の解釈をまとめています。

判定値	解釈
0	最も信頼性の高い 0
1	2 番目に信頼性の高い 0
2	3 番目に信頼性の高い 0
3	最も信頼性の低い 0
4	最も信頼性の低い 1
5	3 番目に信頼性の高い 1
6	2 番目に信頼性の高い 1
7	最も信頼性の高い 1

トレースバックと復号化の遅延

トレースバック長は復号化遅延に影響を与えます。復号化遅延は、出力の最初に復号化されるシンボルよりも前の 0 シンボルの数です。

• 連続操作モードの場合、復号化遅延はトレースバック長シンボルの数と同じです。

• 打ち切られた操作モードまたは終了した操作モードの場合、復号化遅延は 0 です。この場合、トレースバック長は、各入力のシンボルの数以下でなければなりません。

トレースバック長の推定値

一般的な推定として、標準のトレースバック長の値は (ConstraintLength – 1) / (1 – coderate) の約 2 倍から 3 倍になります。符号の拘束長 ConstraintLength は (log2(trellis.numStates) + 1) に等しくなります。coderate は (K / N) × (length(PuncturePattern) / sum(PuncturePattern) に等しくなります。

K は入力シンボルの数、N は出力シンボルの数、および PuncturePattern はパンクチャ パターン ベクトルです。

たとえば、この一般的な推定を適用することで、次のようなおおよそのトレースバック長が得られます。

• 符号化率 1/2 の符号のトレースバック長は 5(ConstraintLength – 1) です。

• 符号化率 2/3 の符号のトレースバック長は 7.5(ConstraintLength – 1) です。

• 符号化率 3/4 の符号のトレースバック長は 10(ConstraintLength – 1) です。

• 符号化率 5/6 の符号のトレースバック長は 15(ConstraintLength – 1) です。

Viterbi Decoder ブロックの [Traceback depth] パラメーターは復号化の遅延を表します。ハードウェア実装によっては 48 および 96 のオプションが用意されている場合があります。この例で 48 が選択されているのは、拘束長が 7 で符号化率が ½ の符号で推測されるターゲットに近いためです。

受信データの遅延

Error Rate Calculation ブロックの [Receive delay] パラメーターは非ゼロです。これは、指定されたメッセージ ビットとそれに対応する復元ビットが非ゼロのシミュレーション時間量で区切られるためです。[Receive delay] パラメーターはエラーのチェック時に、ブロックに比較する入力信号の要素を伝えます。

この場合、受信遅延値はトレースバック長の値 (48) と等しくなります。

シミュレーション結果を論理上の結果と比較

この節では、このシミュレーションでのビット エラー レートと非量子化復号化から論理的に得たビット エラー レートとの比較方法を説明します。処理には以下のステップが含まれます。

• ビット エラー レートの理論的な限界を計算

  このモデルの畳み込み符号のビット エラー レート P_b の理論的な限界を計算するには、非量子化判定復号化に基づいたこの推定を使用します。

  $$P_b<{\displaystyle \sum _{d=f}^{\infty }{c}_d{P}_d}$$

  この推定では、c_d は距離 d の誤りイベントのビット誤りの総数を表し、f はその符号の自由距離を表します。量 P_d はペアワイズ誤り確率で、次式で与えられます。

  $$P_d=\frac{1}{2}\mathrm{erfc}\left(\sqrt{dR\frac{E_b}{N_0}}\right)$$

  ここで、R は 1/2 の符号化率で、erfc は MATLAB 相補誤差関数で、次式で定義されます。

  $$\mathrm{erfc}(x)=\frac{2}{\sqrt{\pi }}{\displaystyle \underset{x}{\overset{\infty }{\int }}{e}^{-t^2}dt}$$

  係数 c_d の値と自由距離 f は、“Convolutional Codes with Optimum Distance Spectrum”[3]などの刊行物に記載されています。この符号の自由距離は f = 10 です。

  次のコマンドは E_b/N₀ 値に対する P_b の値を 1 ～ 4 まで 0.5 の増分で計算します。

  EbNoVec = [1:0.5:4.0];
  R = 1/2;
  % Errs is the vector of sums of bit errors for
  % error events at distance d, for d from 10 to 29.
  Errs = [36 0 211 0 1404 0 11633 0 77433 0 502690 0,...
          3322763 0 21292910 0 134365911 0 843425871 0]; 
  % P is the matrix of pairwise error probilities, for
  % Eb/No values in EbNoVec and d from 10 to 29.
  P = zeros(20,7); % Initialize.
  for d = 10:29
     P(d-9,:) = (1/2)*erfc(sqrt(d*R*10.^(EbNoVec/10)));
  end
  % Bounds is the vector of upper bounds for the bit error
  % rate, for Eb/No values in EbNoVec.
  Bounds = Errs*P;

• ビット エラー レートを収集するためにシミュレーションを複数回実行

  関数 sim (Simulink) を使用して MATLAB コマンド ラインからシミュレーションを実行して、シミュレーション パラメーターを効果的に変化させることができます。たとえば、次のコードは 1 dB ～ 4 dB まで 0.5 dB の増分で 1 ビットあたりのエネルギー対ノイズの比でビット エラー レートを計算します。このコードは BERVec 行列でこれらのシミュレーションからすべてのビット エラー レートを収集します。また、上記のコード部分で計算された理論的な範囲に加えて、Figure ウィンドウでビット エラー レートもプロットします。

  この例では、シミュレーションの概要で説明されているモデルを使用して、符号化率 1/2 の畳み込み符号をシミュレートします。以下のコード サンプルにおいて、モデル名 doc_softdecision は、シミュレーションの概要で説明されているモデルを表します。

  % Plot theoretical bounds and set up figure.
  figure;
  semilogy(EbNoVec,Bounds,'bo',1,NaN,'r*');
  xlabel('Eb/No (dB)'); ylabel('Bit Error Rate');
  title('Bit Error Rate (BER)');
  l = legend('Theoretical bound on BER','Actual BER');
  l.AutoUpdate = 'off';
  axis([1 4 1e-5 1]);
  hold on;
  
  BERVec = [];
  % Make the noise level variable.
  set_param('doc_softdecision/AWGN Channel',...
      'EsNodB','EbNodB+10*log10(1/2)');
  % Simulate multiple times.
  for n = 1:length(EbNoVec)
      EbNodB = EbNoVec(n);
      sim('doc_softdecision',5000000);
      BERVec(n,:) = BER_Data;
      semilogy(EbNoVec(n),BERVec(n,1),'r*'); % Plot point.
      drawnow;
  end
  hold off;

  メモ

  P_b の推定は、復号化器が非量子化データ、つまり、無限に存在する微細な量子化を使用すると仮定します。一方、この例におけるシミュレーションでは 8 レベル (3 ビット) の量子化を使用しています。この量子化のため、シミュレートされたビット エラー レートは S/N 比が高い場合の範囲ほど低くありません。

  S/N 比に対するビット エラー レートのプロットが後に続きます。シミュレーションでは乱数が使用されるため、実際の BER 点の位置は異なる場合があります。

  

MATLAB を使用した符号化率 -2/3 のフィードフォワード符号化器の設計

次の例は、下図に示すような符号化率 2/3 のフィードフォワード符号化器を使います。ここでの説明には、符号化器の図からトレリス パラメーターを決定する方法と、この符号化器を使った符号化方法が示されています。

符号化パラメーターの決定.  パラメーターが適切な値をもつ場合、関数 convenc および vitdec は、このコードを実装できます。

符号化器は 2 つの入力をもつので、符号化器の拘束長は、長さ 2 のベクトルです。このベクトルの要素は、現在の入力ビットを含む各シフト レジスタに格納されたビット数を示します。図の各シフト レジスタ内のメモリ空間の数に、現在の入力として 1 を加えて、拘束長は [5 4] になります。

符号生成パラメーターを 8 進数からなる 2 行 3 列の行列として決定するには、i 番目の入力が j 番目の出力にどのように寄与するかを示すために i 行 j 列の要素を使います。たとえば、2 行 3 列の要素を計算するには、図の 2 番目のシフト レジスタの最も左の要素と最も右の 2 つの要素の和が 3 番目の出力になります。この情報を 2 進数 1011 つまり 8 進数 13 として取得します。符号生成行列の全部の値は、[23 35 0; 0 5 13] です。

関数 convenc および vitdec において拘束長と符号生成パラメーターを使用するには、それらのパラメーターをトレリス構造体に変換する関数 poly2trellis を使用します。これを行うコマンドは、以下のとおりです。

trel = poly2trellis([5 4],[23 35 0;0 5 13]); % Define trellis.

符号化器の使用.  次に、この符号化器を使用したスクリプトを示します。

len = 1000;

msg = randi([0 1],2*len,1); % Random binary message of 2-bit symbols
trel = poly2trellis([5 4],[23 35 0;0 5 13]); % Trellis
% Create a ConvolutionalEncoder System object
hConvEnc = comm.ConvolutionalEncoder(trel);
% Create a ViterbiDecoder System object
hVitDec = comm.ViterbiDecoder(trel, 'InputFormat', 'hard', ...
    'TracebackDepth', 34, 'TerminationMethod', 'Continuous');
% Create a ErrorRate Calculator System object. Since each symbol represents
% two bits, the receive delay for this object is twice the traceback length
% of the viterbi decoder.
hErrorCalc = comm.ErrorRate('ReceiveDelay', 68);
ber = zeros(3,1); % Store BER values
code = step(hConvEnc,msg); % Encode the message.
ncode = rem(code + randerr(3*len,1,[0 1;.96 .04]),2); % Add noise.
decoded = step(hVitDec, ncode); % Decode.
ber = step(hErrorCalc, msg, decoded);

convenc は、2 ビット シンボルを含むベクトルを受け取り、3 ビット シンボルを含むベクトルを生成します。vitdec は、その逆の処理を実行します。また biterr は decoded の最初の 68 要素を無視することにも注意してください。つまり、復号化遅延は 68 で、これは復元されたメッセージのシンボルあたりのビット数 (2) と、関数 vitdec のトレースバック長の値 (34) を乗算した値です。decoded の最初の 68 要素は 0 で、その後の要素が復号化されたメッセージを表します。

Simulink を使用した符号化率 2/3 のフィードフォワード符号化器の設計

この例では、下図の符号化率 2/3 のフィードフォワード畳み込み符号化器を使用します。ここでの説明には、符号化率 2/3 のフィードフォワード符号化器の図から符号化ブロックのパラメーターを特定する方法が示されています。この例では、受信遅延が発生した場合の Error Rate Calculation ブロックの使用についても示しています。

符号化パラメーターの特定方法.  パラメーターが適切な値をもつ場合、Convolutional Encoder および Viterbi Decoder ブロックは、この符号を実装できます。

符号化器は 2 つの入力をもつので、符号化器の拘束長は、長さ 2 のベクトルです。このベクトルの要素は、現在の入力ビットを含む各シフト レジスタに格納されたビット数を示します。図の各シフト レジスタ内のメモリ空間の数に、現在の入力として 1 を加えて、拘束長は [5 4] になります。

符号生成パラメーターを 8 進数からなる 2 行 3 列の行列として決定するには、i 番目の入力が j 番目の出力にどのように寄与するかを示すために i 行 j 列の要素を使います。たとえば、2 行 3 列の要素を計算するには、図の 2 番目のシフト レジスタの最も左の要素と最も右の 2 つの要素の和が 3 番目の出力になります。この情報を 2 進数 1011 つまり 8 進数 13 として取得します。符号生成行列の全部の値は、[27 33 0; 0 5 13] です。

Convolutional Encoder および Viterbi Decoder ブロックにおいて拘束長と符号生成パラメーターを使用するには、それらのパラメーターをトレリス構造体に変換する関数 poly2trellis を使用します。

符号化器のシミュレート方法.  次のモデルはこの符号化器をシミュレートします。

モデルを作成するには、次のブロックを収集し、設定します。

• Bernoulli Binary Generator (パラメーター設定を次のように更新):

  • [Probability of a zero] を .5 に設定します。

  • [Initial seed] を任意の正のスカラー整数 (関数 randn の出力であることが好ましい) に設定します。

  • [Sample time] を .5 に設定します。

  • [Frame-based outputs] チェック ボックスをオンにします。

  • [Samples per frame] を 2 に設定します。

• Convolutional Encoder (パラメーター設定を次のように更新):

  • [Trellis structure] を poly2trellis([5 4],[23 35 0; 0 5 13]) に設定します。

• Channels ライブラリ内の Binary Symmetric Channel

  • [Error probability] を 0.02 に設定します。

  • [Initial seed] を任意の正のスカラー整数 (関数 randn の出力であることが好ましい) に設定します。

  • [Output error vector] チェック ボックスをオフにします。

• Viterbi Decoder (パラメーター設定を次のように更新):

  • [Trellis structure] を poly2trellis([5 4],[23 35 0; 0 5 13]) に設定します。

  • [Decision type] を [Decision type] に設定します。

• Error Rate Calculation (パラメーター設定を次のように更新):

  • [Receive delay] を 68 に設定します。

  • [Output data] を [Port] に設定します。

  • [Stop simulation] チェック ボックスをオンにします。

  • [Target number of errors] を 100 に設定します。

• Display (Simulink)

  • 3 つのエントリが表示されるようにアイコンの下端をドラッグします。

前の図に示したようにブロックを接続します。[シミュレーション] タブの [シミュレーション] セクションで、[終了時間] を inf に設定します。[シミュレーション] セクションは複数のタブに表示されます。

モデルについての注釈.  モデル内の信号の行列サイズを表示することができます。[デバッグ] タブで、[情報のオーバーレイ] を展開します。[信号] セクションで、[信号の次元] を選択します。

符号化器は 2 行 1 列の列ベクトルを受け入れ、3 行 1 列の列ベクトルを生成するのに対し、復号化器はその反対の操作を行います。Bernoulli Binary Generator ブロックの [Samples per frame] パラメーターは、ブロックが長さ 2 のメッセージ ワードを生成しなければならないため 2 に指定されます。

Error Rate Calculation ブロックの [Receive delay] パラメーターは 68 です。この値は、Viterbi Decoder ブロックで復元されたメッセージのベクトル長 (2) に [Traceback depth] 値 (34) を掛けたものです。MATLAB ワークスペースで送信信号と受信信号を行列として調べると、復元されたメッセージの最初の 34 行はゼロになっており、後続の行は復号化されたメッセージを表します。したがって、受信信号での遅延は長さ 2 の 34 ベクトル (68 サンプル) です。

モデルを実行すると、3 つの数字からなる表示出力が生成されます。つまり、エラー レート、誤りの総数、Error Rate Calculation ブロックがシミュレーション時に行う比較の総数が生成されます (最初の 2 つの数字は、Bernoulli Binary Generator および Binary Symmetric Channel ブロックの [Initial seed] 値によって異なります)。シミュレーションは 100 の誤りが発生した後で停止します。これは、[Target number of errors] が Error Rate Calculation ブロックで 100 に設定されているためです。エラー レートは Binary Symmetric Channel ブロックの [Error probability] の 0.02 よりはるかに小さいです。

MATLAB を使用した畳み込み符号のパンクチャ

この例では、パンクチャド畳み込み符号の処理を行います。まず、30,000 個のランダムなビットを作成し、[1 1 1 0 0 1] のパンクチャ パターンをもつ符号化率 -3/4 の畳み込み符号化器で符号化します。結果のベクトルは、40,000 ビットを含み、これは伝送用に値 -1 と 1 にマッピングされます。パンクチャド符号 punctcode は加法性ホワイト ガウス ノイズチャネルを通過します。次に、vitdec は、'unquant' 判定タイプを使用してノイズのあるベクトルを復号化します。

最後に、例ではビット エラー レートとビット誤りの数を計算します。

len = 30000; msg = randi([0 1], len, 1); % Random data
t = poly2trellis(7, [133 171]); % Define trellis.
% Create a ConvolutionalEncoder System object
hConvEnc = comm.ConvolutionalEncoder(t, ...
    'PuncturePatternSource', 'Property', ...
    'PuncturePattern', [1;1;1;0;0;1]);
% Create an AWGNChannel System object.
hChan = comm.AWGNChannel('NoiseMethod', 'Signal to noise ratio (SNR)',...
  'SNR', 3);
% Create a ViterbiDecoder System object
hVitDec = comm.ViterbiDecoder(t, 'InputFormat', 'Unquantized', ...
    'TracebackDepth', 96, 'TerminationMethod', 'Truncated', ...
    'PuncturePatternSource', 'Property', ...
    'PuncturePattern', [1;1;1;0;0;1]);
% Create a ErrorRate Calculator System object.
hErrorCalc = comm.ErrorRate;
berP = zeros(3,1); berPE = berP; % Store BER values
punctcode = step(hConvEnc,msg); % Length is (2*len)*2/3.
tcode = 1-2*punctcode; % Map "0" bit to 1 and "1" bit to -1
hChan.SignalPower = (tcode'*tcode)/length(tcode);
ncode = step(hChan,tcode); % Add noise.

% Decode the punctured code
decoded = step(hVitDec,ncode); % Decode.
berP = step(hErrorCalc, msg, decoded);% Bit error rate
% Erase the least reliable 100 symbols, then decode
release(hVitDec); reset(hErrorCalc)
hVitDec.ErasuresInputPort = true;
[dummy idx] = sort(abs(ncode));
erasures =  zeros(size(ncode)); erasures(idx(1:100)) = 1;
decoded = step(hVitDec,ncode, erasures); % Decode.
berPE = step(hErrorCalc, msg, decoded);% Bit error rate

fprintf('Number of errors with puncturing: %d\n', berP(2))
fprintf('Number of errors with puncturing and erasures: %d\n', berPE(2))

Simulink を使用したフィードバックをもつ組織符号化器の実装

この節では、Convolutional Encoder ブロックを使用してフィードバックをもつ組織符号化器を実装する方法を説明します。符号は、実際のメッセージ ワードがコードワードの一部として表示される場合は "組織的" です。次の図は、組織符号化器の例を示しています。

この符号化器を実装するには、Convolutional Encoder ブロックの [Trellis structure] パラメーターを poly2trellis(5, [37 33], 37) に設定します。この設定は以下のように対応します。

• 拘束長: 5

• 生成多項式のペア: [37 33]

• フィードバック多項式: 37

フィードバック多項式は、上列の 2 進数値に対応するバイナリ ベクトル [1 1 1 1 1] によって表されます。これらの数値は、レジスタの出力から加算器への接続を示します。最初の 1 は入力ビットに対応します。2 進数 11111 の 8 進数表現は 37 です。

組織符号を実装するには、最初の生成多項式を Convolutional Encoder ブロックの [Trellis structure] パラメーターにあるフィードバック多項式と同じに設定します。この例では、両方の多項式の 8 進数表現は 37 です。

2 番目の生成多項式は、下列の 2 進数値に対応するバイナリ ベクトル [1 1 0 1 1] によって表されます。2 進数 11011 に対応する 8 進数は 33 です。

Convolutional Encoder ブロックのマスク パラメーターの設定方法の詳細は、畳み込み符号の多項式表現を参照してください。

軟判定復号化

この例では、符号化率 1/2 の畳み込み符号を作成します。軟判定を実行するために、量子化と Viterbi Decoder ブロックを使用します。この説明では、以下のトピックについて説明します。

• シミュレーションの概要

• 畳み込み符号の定義

• 受信データのマッピング

• 畳み込み符号の復号化

• 受信データの遅延

• シミュレーション結果を論理上の結果と比較

シミュレーションの概要.   シミュレーションでは、作成したランダム バイナリ メッセージ信号を畳み込み符号に符号化し、これを 2 位相偏移変調 (BPSK) 手法により変調後、変調されたデータにホワイト ガウス ノイズを追加してノイズのあるチャネルをシミュレートします。次に、復号化ブロック用に受信データを準備し、復号化を行います。最後に、復号化した情報と元のメッセージ信号を比較し、ビット エラー レートを計算します。畳み込み符号化器は、符号化率 1/2 の符号化器として構成されます。この符号化器は、2 ビットごとに別の 2 つの冗長ビットを追加します。これに適合させ、正確な量のノイズを追加するため、AWGN ブロックのパラメーター [Eb/No (dB)] は 10*log10(2) を差し引くことにより実質半分にされます。シミュレーションは 100 個のビット誤りまたは 10⁷ メッセージ ビット (どちらか先に起こった方) を処理した後で終了します。

畳み込み符号の定義.  この例のフィードフォワード畳み込み符号化器を以下に示します。

符号化器は 1 つの入力をもつので、符号化器の拘束長はスカラーです。拘束長の値は、シフト レジスタに格納されたビット数です。これには現在の入力も含まれます。6 つのメモリ レジスタがあり、現在の入力は 1 ビットです。したがって、符号の拘束長は 7 になります。

符号化器は 1 つの入力と 2 つの出力をもつので、符号生成器は 8 進数の 1 行 2 列の行列です。行列内の最初の要素は、最初の出力に関連する入力値を示し、2 番目の要素は、2 番目の出力に関連する入力値を示します。

たとえば、符号化器ダイアグラムの最初の出力は、ダイアグラムの入力値の配列の右端の要素および左端の 4 つの要素の剰余 2 の和です。7 桁の 2 進数 1111001 はこの情報を取得しますが、これは 8 進数の 171 と等価です。したがって、8 進数 171 は、符号生成行列の最初のエントリとなります。ここでは、各 3 桁ビットで最上位ビットとして左端のビットを使用します。2 番目の出力は、2 進数 1011011 に対応します。これは、8 進数 133 に相当します。したがって、符号生成器は [171 133] になります。

Convolutional Encoder ブロックの [Trellis structure] パラメーターは、データ処理にどの符号を使用するかを伝えます。この場合、Communications Toolbox の関数 poly2trellis は、拘束長と 8 進数の組を有効なトレリス構造体に変換します。

Convolutional Encoder ブロックに入るときのメッセージ データはスカラー ビット ストリームですが、ブロックから出てくる符号化済みのデータは、長さ 2 のバイナリ ベクトルのストリームです。

受信データのマッピング.  受信データ、すなわち AWGN Channel ブロックの出力は、-1 および 1 に近い複素数で構成されます。元のバイナリ メッセージを再構築するためには、モデルの受信機部分で畳み込み符号を復号化しなければなりません。このモデルの Viterbi Decoder ブロックでは、入力データが 0 ～ 7 の整数であると想定しています。このモデルのカスタム サブシステムである復調器は、受信データを Viterbi Decoder ブロックが正しく解釈できる形式に変換します。具体的には、復調器サブシステムは以下を行います。

• 虚数部を削除することで、受信データ信号を実信号に変換します。送信されたデータの虚数部はゼロ (小さな丸め誤差は無視) であること、およびチャネル ノイズはあまり強くないことなどの理由で、受信データの虚数部には必須の情報が含まれていないと仮定できます。

• ノイズの推定値の標準偏差で除算し、-1 で乗算することにより、受信データを正規化します。

• 3 つのビットを使用して正規化データを量子化します。

このマッピングと Viterbi Decoder ブロックの判定マッピングの組み合わせにより、このモデルの送信側で BPSK Modulator Baseband ブロックが実行する BPSK 変調が逆になります。復調器サブシステムを詳しく調べるには、[Soft-Output BPSK Demodulator] というラベルのアイコンをダブルクリックします。

畳み込み符号の復号化.  受信データが 3 ビットの判定値をもつ長さ 2 のベクトルに正しくマッピングされると、Viterbi Decoder ブロックによりそれが復号化されます。[Decision type] パラメーターは [Soft Decision] で、[Number of soft decision bits] パラメーターは 3 であるため、ブロックは 2³ の異なる入力値をもつ軟判定アルゴリズムを使用します。

データの軟判定解釈

[Decision type] パラメーターが [Soft Decision] に設定されると、Viterbi Decoder ブロックでは 0 ～ 2^b-1 の入力値が要求されます。ここで、b は [Number of soft decision bits] パラメーターです。ブロックは、0 を、コードワード ビットが 0 であるという最も信頼性の高い判定であると解釈し、2^b-1 を、コードワード ビットが 1 であるという最も信頼性の高い判定であると解釈します。これらの極値の間の値は、それらよりも信頼性の低い判定を表します。次の表は、この例の入力値として使用できる 8 つの値の解釈をまとめています。

判定値	解釈
0	最も信頼性の高い 0
1	2 番目に信頼性の高い 0
2	3 番目に信頼性の高い 0
3	最も信頼性の低い 0
4	最も信頼性の低い 1
5	3 番目に信頼性の高い 1
6	2 番目に信頼性の高い 1
7	最も信頼性の高い 1

トレースバックと復号化の遅延

Viterbi Decoder ブロックの [Traceback depth] パラメーターは復号化の遅延を表します。トレースバック長の典型的な値は拘束長の約 5 ～ 6 倍で、この例では 35 または 42 になります。ただし、ハードウェア実装によっては 48 および 96 のオプションが用意されている場合があります。この例で 48 が選択されているのは、96 よりもターゲット (35 および 42) に近いためです。

受信データの遅延.  Error Rate Calculation ブロックの [Receive delay] パラメーターは非ゼロです。これは、指定されたメッセージ ビットとそれに対応する復元ビットが非ゼロのシミュレーション時間量で区切られるためです。[Receive delay] パラメーターはエラーのチェック時に、ブロックに比較する入力信号の要素を伝えます。

この場合、受信遅延値はトレースバック長の値 (48) と等しくなります。

シミュレーション結果を論理上の結果と比較.  この節では、このシミュレーションでのビット エラー レートと非量子化復号化から論理的に得たビット エラー レートとの比較方法を説明します。このプロセスには以下の節で説明されているいくつかの手順が含まれます。

ビット エラー レートの理論的な限界を計算

このモデルの畳み込み符号のビット エラー レート P_b の理論的な限界を計算するには、非量子化判定復号化に基づいたこの推定を使用します。

$$P_b<{\displaystyle \sum _{d=f}^{\infty }{c}_d{P}_d}$$

この推定では、c_d は距離 d の誤りイベントのビット誤りの総数を表し、f はその符号の自由距離を表します。量 P_d はペアワイズ誤り確率で、次式で与えられます。

$$P_d=\frac{1}{2}\mathrm{erfc}\left(\sqrt{dR\frac{E_b}{N_0}}\right)$$

ここで、R は 1/2 の符号化率で、erfc は MATLAB 相補誤差関数で、次式で定義されます。

$$\mathrm{erfc}(x)=\frac{2}{\sqrt{\pi }}{\displaystyle \underset{x}{\overset{\infty }{\int }}{e}^{-t^2}dt}$$

係数 c_d の値と自由距離 f は、“Convolutional Codes with Optimum Distance Spectrum”[3]などの刊行物に記載されています。この符号の自由距離は f = 10 です。

次のコマンドは E_b/N₀ 値に対する P_b の値を 1 ～ 4 まで 0.5 の増分で計算します。

EbNoVec = [1:0.5:4.0];
R = 1/2;
% Errs is the vector of sums of bit errors for
% error events at distance d, for d from 10 to 29.
Errs = [36 0 211 0 1404 0 11633 0 77433 0 502690 0,...
        3322763 0 21292910 0 134365911 0 843425871 0]; 
% P is the matrix of pairwise error probilities, for
% Eb/No values in EbNoVec and d from 10 to 29.
P = zeros(20,7); % Initialize.
for d = 10:29
   P(d-9,:) = (1/2)*erfc(sqrt(d*R*10.^(EbNoVec/10)));
end
% Bounds is the vector of upper bounds for the bit error
% rate, for Eb/No values in EbNoVec.
Bounds = Errs*P;

ビット エラー レートを収集するためにシミュレーションを複数回実行

関数 sim (Simulink) を使用して MATLAB コマンド ラインからシミュレーションを実行して、シミュレーション パラメーターを効果的に変化させることができます。たとえば、次のコードは 1 dB ～ 4 dB まで 0.5 dB の増分で 1 ビットあたりのエネルギー対ノイズの比でビット エラー レートを計算します。このコードは BERVec 行列でこれらのシミュレーションからすべてのビット エラー レートを収集します。また、上記のコード部分で計算された理論的な範囲に加えて、Figure ウィンドウでビット エラー レートもプロットします。

以下のコード サンプルにおいて、モデル名 doc_softdecision は、シミュレーションの概要で説明されているモデルを表します。

メモ

P_b の推定は、復号化器が非量子化データ、つまり、無限に存在する微細な量子化を使用すると仮定します。一方、この例におけるシミュレーションでは 8 レベル (3 ビット) の量子化を使用しています。この量子化のため、シミュレートされたビット エラー レートは S/N 比が高い場合の範囲ほど低くありません。

S/N 比に対するビット エラー レートのプロットが後に続きます。シミュレーションでは乱数が使用されるため、実際の BER 点の位置は異なる場合があります。

フィードバック符号化器を使用したテールバイト符号化

この例は、フィードバック符号化器を使用したテールバイト符号化を示しています。フィードバック符号化器では、終了状態はデータ ブロック全体に依存します。テールバイトを実行するには、特定の情報ベクトル (N ビット) に対し、データ ブロックの符号化後に同じ終了状態をもたらす初期状態を計算しなければなりません。

このためには次の 2 つの手順を実行します。

• 最初の手順では、特定のデータ ブロックに対して 0 の状態応答を指定します。符号化器はすべて 0 の状態で開始します。データ ブロック全体が入力され、出力ビットは無視されます。N ビット後に、符号化器は X_N ^[zs] 状態になります。この状態から、対応する初期状態 X₀ を計算し、X₀ で符号化器を初期化します。

• 2 番目の手順では、実際に符号化を行います。符号化器は初期状態 X₀ から開始されます。データ ブロックが入力され、有効なコードワードは出力され、同じ状態の境界条件に一致します。

状態空間形式の公式を使用して X_N ^[zs] から初期状態 X₀ を理論的に計算するには、[8] を参照してください。これはブロック長を使用した 1 回限りの計算であり、実際にはルックアップ テーブルとして実装できます。ここでは、選択したトレイルとブロック長に使用可能なすべてのエントリをシミュレートすることで、このマッピング テーブルを決定します。

ブロックを組み合わせてモデルを作成します。以下のコード サンプルにおいて、モデル名 doc_mtailbiting_wfeedback は、図で説明されているモデルを表します。

function mapStValues = getMapping(blkLen, trellis)
% The function returns the mapping value for the given block
length and trellis to be used for determining the initial
state from the zero-state response.

% All possible combinations of the mappings
mapStValuesTab = perms(0:trellis.numStates-1);

% Loop over all the combinations of the mapping entries:
for i = 1:length(mapStValuesTab)
mapStValues = mapStValuesTab(i,:);

% Model parameterized for the Block length
sim('mtailbiting_wfeedback');

% Check the boundary condition for each run
% if ending and starting states match, choose that mapping set
if unique(out)==0
        return
    end
end

Lookup サブシステムの Direct Lookup Table (n-D) ブロックの [テーブル データ] パラメーターに対して返される mapStValues を選択すると、選択したブロック長とトレイルのテールバイト符号化が実行されます。

畳み込み符号化の参考文献

[1] Clark, George C. Jr., and J. Bibb Cain, Error-Correction Coding for Digital Communications, New York, Plenum Press, 1981.

[2] Gitlin, Richard D., Jeremiah F. Hayes, and Stephen B. Weinstein, Data Communications Principles, New York, Plenum Press, 1992.

[3] Frenger, P., P. Orten, and T. Ottosson. “Convolutional Codes with Optimum Distance Spectrum.” IEEE Communications Letters 3, no. 11 (November 1999): 317–19. https://doi.org/10.1109/4234.803468.

線形ブロック符号

• 線形ブロック符号に対するワードの表現

• 線形ブロック符号のパラメーターの設定

• 線形ブロック符号の作成と復号化

線形ブロック符号に対するワードの表現

この製品の巡回、ハミング、および一般線形ブロック符号の機能は、メッセージまたはコードワードのビットをまとめる方法を複数提供します。以下のトピックでは、使用可能な形式を説明します。

• MATLAB を使用したメッセージとコードワードのバイナリ ベクトル形式での作成

• MATLAB を使用したメッセージとコードワードのバイナリ行列形式での作成

• MATLAB を使用したメッセージとコードワードの 10 進数ベクトル形式での作成

BCH またはリード・ソロモン符号に対するワードを表す方法の詳細は、BCH 符号に対するワードの表現またはリード・ソロモン符号のワードの表現を参照してください。

MATLAB を使用したメッセージとコードワードのバイナリ ベクトル形式での作成.  メッセージとコードワードは、0 と 1 で構成されるベクトルの形式です。たとえば、メッセージとコードは、以下の行に示す msg や code のようになります。

n = 6; k = 4; % Set codeword length and message length
% for a [6,4] code.
msg = [1 0 0 1 1 0 1 0 1 0 1 1]'; % Message is a binary column.
code = encode(msg,n,k,'cyclic'); % Code will be a binary column.
msg'
code'

出力は以下のようになります。

ans =

  Columns 1 through 5

      1            0            0            1            1

  Columns 6 through 10

      0            1            0            1            0

  Columns 11 through 12

      1            1


ans =

  Columns 1 through 5

      1            1            1            0            0

  Columns 6 through 10

      1            0            0            1            0

  Columns 11 through 15

      1            0            0            1            1

  Columns 16 through 18

      0            1            1      

この例では、msg は、3 つの 4 桁 (k = 4) のメッセージとして解釈される 12 のエントリで構成されます。結果のベクトル code は、長さ 18 のベクトルを形成する連結した 3 つの 6 桁 (n = 6) のコードワードで構成されます。パリティ ビットは、各コードワードの先頭にあります。

MATLAB を使用したメッセージとコードワードのバイナリ行列形式での作成.  符号化情報を整理して、桁数をメッセージとコードワードに明確に分けることができます。このアプローチを使用する場合は、各メッセージまたはコードワードはバイナリ行列内の 1 行を占めます。以下の例では、msg の各行に 4 ビットのメッセージをリストし、code の各行に 6 ビットのコードワードをリストして、このアプローチを示します。

n = 6; k = 4; % Set codeword length and message length.
msg = [1 0 0 1; 1 0 1 0; 1 0 1 1]; % Message is a binary matrix.
code = encode(msg,n,k,'cyclic'); % Code will be a binary matrix.
msg
code

出力は以下のようになります。

msg =

     1     0     0     1
     1     0     1     0
     1     0     1     1


code =

     1     1     1     0     0     1
     0     0     1     0     1     0
     0     1     1     0     1     1

メモ

バイナリ行列の形式では、メッセージ行列には k 列が必要です。対応する符号行列は、n 列あります。パリティ ビットは、各行の先頭にあります。

MATLAB を使用したメッセージとコードワードの 10 進数ベクトル形式での作成.  メッセージとコードワードは、整数からなるベクトルの形式です。ベクトルの各要素は、1 つのメッセージまたは 1 つのコードワード内のビットの 10 進数表現を示します。

メモ

2^n または 2^k が非常に大きい場合、10 進数の形式ではなく既定のバイナリ形式を使用する必要があります。これは、関数は内部的にバイナリ形式を使っており、多くのビットを大きい 10 進数に変換することに対応する丸め誤差が大きくなるためです。

メモ

10 進数のベクトル形式を使用する場合、encode では、"最も左側" のビットが最下位ビットであることが予期されます。

encode コマンドの構文は、10 進数形式を以下の例のように明示的に示さなければなりません。/decimal が encode コマンドの 4 番目の引数に付加されることに注意してください。

n = 6; k = 4; % Set codeword length and message length.
msg = [9;5;13]; % Message is a decimal column vector.
% Code will be a decimal vector.
code = encode(msg,n,k,'cyclic/decimal')

出力は以下のようになります。

code =

    39
    20
    54

メモ

上の 3 つの例では、巡回符号化を使用しました。メッセージとコードの形式は、ハミングおよび一般線形ブロック符号に対しても同じです。

線形ブロック符号のパラメーターの設定

このサブセクションでは、[n,k] 巡回、ハミング、一般線形ブロック符号を処理するために必要な項目を説明します。次の表は、最も関連する項目と符号化手法をまとめています。

ブロック符号化手法で使用されるパラメーター

パラメーター	ブロック符号化手法
生成行列	一般線形ブロック
パリティ チェック行列	一般線形ブロック
生成多項式	巡回
MATLAB での復号化テーブルの使用	一般線形ブロック、ハミング

生成行列.  [n,k] 線形ブロック符号にメッセージを符号化する処理は、k 行 n 列の生成行列 G によって決定されます。特に、1 行 k 列のメッセージ ベクトル v は、1 行 n 列のコードワード ベクトル vG に符号化されます。G が形式 [I_k P] または [P I_k] をもつ場合、ここで P は適当な k 行 (n-k) 列の行列で I_k は k 行 k 列の単位行列ですが、G は "標準形" と呼ばれます(著者によって、Clark and Cain[2]のように最初の標準形を使用する場合も、Lin and Costello[3]のように後者を使用する場合もあります)。このツールボックスのほとんどの関数では、入力引数として使用する生成行列は標準形であると仮定します。

生成行列の例は、次の節パリティ チェック行列で示します。

パリティ チェック行列.  [n,k] 線形ブロック符号の復号化では、(n-k) 行 n 列パリティ チェック行列 H を必要とします。GH^tr = 0 (mod 2) が成り立ちます。ここで、H^tr は行列 H の転置を示し、G は符号の生成行列であり、このゼロ行列は k 行 (n-k) 列です。G = [I_k P] の場合、H = [-P^tr I_n-k] です。この製品のほとんどの関数では、入力引数として使用するパリティ チェック行列は標準形であると仮定します。

次の表は、[n,k] バイナリ線形ブロック符号に対する生成行列とパリティ チェック行列の標準形をまとめています。

行列の種類	標準形	次元
生成行列	[Ik P] または [P Ik]	k 行 n 列
パリティ チェック行列	[-P' In-k] または [In-k -P' ]	(n-k) 行 n 列

I_k はサイズ k の単位行列であり、シンボル ' は行列の転置を示します ("2 値" 符号に対して、上記のパリティ チェック形式のマイナス符号は意味がありません。つまり、バイナリ フィールドでは -1 = 1 です)。

例

以下のコマンドで、parmat はパリティ チェック行列で、genmat は [n,k] = [2³-1, n-3] = [7,4] であるハミング符号の生成行列です。genmat は標準形 [P I_k] をもちます。

[parmat,genmat] = hammgen(3)
parmat =

     1     0     0     1     0     1     1
     0     1     0     1     1     1     0
     0     0     1     0     1     1     1

genmat =

     1     1     0     1     0     0     0
     0     1     1     0     1     0     0
     1     1     1     0     0     1     0
     1     0     1     0     0     0     1

次の例では、[7,3] 巡回符号に対するパリティ チェック行列および生成行列を求めます。関数 cyclpoly の詳細は、以下の生成多項式を参照してください。

genpoly = cyclpoly(7,3);
[parmat,genmat] = cyclgen(7,genpoly)
parmat =

     1     0     0     0     1     1     0
     0     1     0     0     0     1     1
     0     0     1     0     1     1     1
     0     0     0     1     1     0     1

genmat =

     1     0     1     1     1     0     0
     1     1     1     0     0     1     0
     0     1     1     1     0     0     1

以下の例では、[5,3] 線形ブロック符号の生成行列を対応するパリティ チェック行列に変換します。

genmat = [1 0 0 1 0; 0 1 0 1 1; 0 0 1 0 1];
parmat = gen2par(genmat)

parmat =

     1     1     0     1     0
     0     1     1     0     1

同じ関数 gen2par で、パリティ チェック行列から生成行列に変換することもできます。

生成多項式.  巡回符号は、多項式が符号化過程を完全に決定できるような代数的性質をもちます。このいわゆる "生成多項式" は、多項式 xⁿ-1 の (n-k) 次除算子です。Van Lint の[5]では、生成多項式が巡回符号をどのように決定するかを説明しています。

関数 cyclpoly は、巡回符号に対する生成多項式を作成します。cyclpoly は、多項式の係数を変数の "昇べき" の順にリストする行ベクトルを使用して生成多項式を表します。たとえば、次のコマンド

genpoly = cyclpoly(7,3)

genpoly =

     1     0     1     1     1

このコマンドは、[7,3] 巡回符号に対する有効な生成多項式が 1 + x² + x³ + x⁴ であることを求めます。

MATLAB での復号化テーブルの使用

復号化テーブルは、伝送中に生じた符号誤りを訂正する方法を復号化器に示します。ハミング符号は、任意のコードワード内の単一シンボルの誤りを訂正することができます。その他の符号は、指定されたコードワード内の複数のシンボルで発生した誤りを訂正、または部分的に訂正します。

このツールボックスは、復号化テーブルを "n" 列 2^(n-k) 行の行列として表します。各行は、受信したコードワード ベクトルに対して訂正ベクトルを指定します。ハミング復号化テーブルには n+1 行あります。関数syndtableは、パリティチェック行列に対する復号化テーブルを生成します。

この例では、受信メッセージ内の誤り訂正のためハミング復号化テーブルを使用します。関数hammgenはパリティ チェック行列を生成し、関数 syndtable は復号化テーブルを生成します。シンドロームを決定するため、パリティ チェック行列の転置を、受信したコードワードで左乗算します。 復号化テーブルは、訂正ベクトルの決定に役立ちます。訂正されたコードワードは、訂正ベクトルと受信したコードワードの和 (剰余 2) です。

[7,4] ハミング コードのパラメーターを設定します。

m = 3; 
n = 2^m-1; 
k = n-m;

パリティ チェック行列と復号化テーブルを生成します。

parmat = hammgen(m);    
trt = syndtable(parmat);

受信データのベクトルを指定します。

recd = [1 0 0 1 1 1 1]

recd = 1×7

     1     0     0     1     1     1     1

シンドロームを計算し、シンドロームの 10 進数値と 2 進数値を表示します。

syndrome = rem(recd * parmat',2);
syndrome_int = bit2int(syndrome',m); % Convert to decimal.
disp(['Syndrome = ',num2str(syndrome_int),...
      ' (decimal), ',num2str(syndrome),' (binary)'])

Syndrome = 3 (decimal), 0  1  1 (binary)

復号化テーブルとシンドロームを使用して訂正ベクトルを決定し、訂正ベクトルを使用して訂正されるコードワードを計算します。

corrvect = trt(1+syndrome_int,:)

corrvect = 1×7

     0     0     0     0     1     0     0

correctedcode = rem(corrvect+recd,2)

correctedcode = 1×7

     1     0     0     1     0     1     1

線形ブロック符号の作成と復号化

巡回、ハミング、および一般線形ブロック符号の符号化と復号化のための関数は、encode と decode です。この節では、一般線形ブロック符号、巡回符号、ハミング符号を作成し、復号化するために、これらの関数の使用方法を説明します。

一般線形ブロック符号.  一般線形ブロック符号を使ってメッセージを符号化するには、生成行列が必要です。変数 msg、n、k、および genmat を定義している場合を考えてみます。

code = encode(msg,n,k,'linear',genmat);
code = encode(msg,n,k,'linear/decimal',genmat);

上記のいずれかのコマンドは、生成行列 genmat が決定する [n,k] 符号を使用して、msg 内の情報を符号化します。2^n と 2^k があまり大きくない場合に適している /decimal オプションは、msg が 2 進数表現以外の負でない 10 進数整数を含むことを示します。msg および code の形式の詳細は、線形ブロック符号に対するワードの表現または関数 encode のリファレンス ページを参照してください。

復号化には、生成行列が必要であり、場合によっては復号化テーブルも必要です。変数 code、n、k、および genmat に加えて、trt も定義している場合を考えてみます。

newmsg = decode(code,n,k,'linear',genmat);
newmsg = decode(code,n,k,'linear/decimal',genmat);
newmsg = decode(code,n,k,'linear',genmat,trt);
newmsg = decode(code,n,k,'linear/decimal',genmat,trt);

上記のコマンドは、生成行列 genmat が決定する [n,k] 符号を使用して code 内の情報を復号化します。decode は、trt が表す復号化テーブルの指示に従って誤りを訂正します。

例:一般線形ブロック符号化

下記の例は、メッセージを符号化し、人工的にノイズを付加し、ノイズを含む符号を復号化し、復号化器が途中で検出する誤りを記録します。復号化テーブルはゼロのみを含むので、復号化器は誤りを訂正しません。

n = 4; k = 2;
genmat = [[1 1; 1 0], eye(2)]; % Generator matrix
msg = [0 1; 0 0; 1 0]; % Three messages, two bits each
% Create three codewords, four bits each.
code = encode(msg,n,k,'linear',genmat);
noisycode = rem(code + randerr(3,4,[0 1;.7 .3]),2); % Add noise.
trt = zeros(2^(n-k),n);  % No correction of errors
% Decode, keeping track of all detected errors.
[newmsg,err] = decode(noisycode,n,k,'linear',genmat,trt);
err_words = find(err~=0) % Find out which words had errors.

出力は、最初と 2 番目のワードで誤りが発生したことを示します。この例では誤りとして乱数を使用するため、結果は異なることがあります。

err_words =

     1
     2

巡回符号.  巡回符号は、(一連のビットで表現された) コードワードの巡回シフトもコードワードであるという性質をもつ線形ブロック符号です。巡回符号の他の特性は、生成多項式と[5]で説明するように、その生成多項式に基づきます。

巡回符号を使ったメッセージの符号化には、生成多項式が必要です。変数 msg、n、k、および genpoly を定義している場合を考えてみます。

code = encode(msg,n,k,'cyclic',genpoly);
code = encode(msg,n,k,'cyclic/decimal',genpoly);

上記のいずれかのコマンドは、生成多項式 genpoly によって決定される [n,k] 符号を使用して msg 内の情報を符号化します。genpoly は、encode のオプションの引数です。既定の生成多項式は cyclpoly(n,k) です。2^n と 2^k があまり大きくない場合に適している /decimal オプションは、msg が 2 進数表現以外の負でない 10 進数整数を含むことを示します。msg および code の形式の詳細は、線形ブロック符号に対するワードの表現または関数 encode のリファレンス ページを参照してください。

復号化には、生成多項式が必要であり、場合によっては復号化テーブルも必要です。変数 code、n、k、genpoly、および trt を定義している場合を考えてみます。

newmsg = decode(code,n,k,'cyclic',genpoly);
newmsg = decode(code,n,k,'cyclic/decimal',genpoly);
newmsg = decode(code,n,k,'cyclic',genpoly,trt);
newmsg = decode(code,n,k,'cyclic/decimal',genpoly,trt);

上記のコマンドは、生成行列 genmat が決定する [n,k] 符号を使用して code 内の情報を復号化します。decode は、trt が表す復号化テーブルの指示に従って誤りを訂正します。genpoly は、上記の最初の 2 つの構文のオプションの引数です。既定の生成多項式は cyclpoly(n,k) です。

例

一般線形ブロック符号の例では、生成行列 genmat を使った線形ブロック符号の代わりに、巡回符号化手法を使うように変更できます。以下のように変更を行います。

• 2 行目を以下で置き換えます。

  genpoly = [1 0 1]; % generator poly is 1 + x^2

• 5 行目と 9 行目 (encode コマンドと decode コマンド) で、genmat を genpoly で置き換え、'linear' を 'cyclic' で置き換えます。

巡回符号および復号化のもう 1 つの例は、関数 encode のリファレンス ページにあります。

ハミング符号.  encode と decode のリファレンス ページには、ハミング符号の符号化と復号化の例があります。また、MATLAB での復号化テーブルの使用では、ハミング符号の誤り訂正を説明します。

ハミング符号

• Simulink を使用したバイナリ形式でのハミング符号の作成

• ハミング符号を使用してエラー レートを減らす

Simulink を使用したバイナリ形式でのハミング符号の作成

この例では、符号化器と復号化器を使用する方法を非常に簡単に示します。符号化ブロックに対する符号とメッセージ信号の適切なベクトル長を示します。Error Rate Calculation ブロックは送信信号と受信信号としてスカラーまたはフレームベースの列ベクトルしか受け取らないため、この例ではフレームベースの列ベクトルを最初から最後まで使用します (したがって、Convert 1-D to 2-D などのブロックを使用して信号属性を変更する必要はありません)。

モデルを作成するには、次のブロックを収集し、設定します。

• Bernoulli Binary Generator (パラメーター設定を次のように更新):

  • [Probability of a zero] を .5 に設定します。

  • [Initial seed] を任意の正のスカラー整数 (関数 randn の出力であることが好ましい) に設定します。

  • [Frame-based outputs] チェック ボックスをオンにします。

  • [Samples per frame] を 4 に設定します。

• Hamming Encoder (既定のパラメーター値を使用)

• Hamming Decoder (既定のパラメーター値を使用)

• Error Rate Calculation (既定のパラメーター値を使用)

前の図に示したようにブロックを接続します。モデル内の信号のベクトル長を表示することができます。[デバッグ] タブで、[情報のオーバーレイ] を展開します。[信号] セクションで、[信号の次元] を選択します。必要に応じてブロック図を更新した後、Ctrl+D を押してモデルをコンパイルし、誤り統計をチェックします。

関連する信号属性が接続線に表示されます。コネクタ ラインはフレームベースの信号を示すように二重線で表示され、行の隣にある注釈は信号が適切なサイズの列ベクトルであることを示します。

ハミング符号を使用してエラー レートを減らす

この節では、誤り修正符号を追加して、エラー レートを減らす方法を説明します。次の図は、ハミング符号を使用するモデルを示します。

ハミング符号モデルの作成

以下の手順に従って、ハミング符号モデルを作成し、作業ファイルを保存するフォルダーにそのモデルを my_hamming という名前で保存します。

1. 新しいモデル ウィンドウを開き、モデルに対応するように必要に応じてウィンドウ領域を拡張します。モデル ウィンドウにブロック名を入力し、Bernoulli Binary Generator、Hamming Encoder、Binary Symmetric Channel、Hamming Decoder、Error Rate Calculation、および Display (Simulink) ブロックを追加します。

2. ブロックを配置して接続し、次のようなモデルを作成します。

   

Hamming Encoder および Decoder ブロックの使用

Hamming Encoder ブロックはデータをチャネル経由で送信する前に符号化します。既定のコードは [7,4] ハミング符号で、このコードは長さ 4 のメッセージ ワードを長さ 7 のコードワードに符号化します。このため、ブロックによってサイズ 4 のフレームはサイズ 7 のフレームに変換されます。コードは送信された各コードワードで 1 つの誤りを修正できます。

[n,k] 符号では、Hamming Encoder ブロックへの入力はサイズ k のベクトルから構成されなければなりません。この例では k = 4 です。

Hamming Decoder ブロックはデータをチャネル経由で送信した後に復号化します。誤りがチャネルによってコードワードで 1 つでも作成されると、ブロックはワードを正しく復号化します。ただし、複数の誤りが生じると、Hamming Decoder ブロックが正しく復号化しない場合があります。

ブロック符号化機能の詳細については、ブロック符号を参照してください。

ハミング符号モデルでのパラメーターの設定

Bernoulli Binary Generator ブロックをダブルクリックし、次の図に示すように、ブロックのダイアログ ボックスのパラメーター設定に次の変更を行います。

1. [Samples per frame] を 4 に設定します。これにより、ブロックの出力がサイズ 4 のフレームに変換され、Hamming Encoder ブロックの入力条件が満たされます。フレームの詳細は、サンプルベースおよびフレームベースの処理を参照してください。

   メモ

   Hamming Encoder ブロックなどの多数のブロックでは、入力を指定のサイズのベクトルに指定する必要があります。Bernoulli Binary Generator ブロックなどのソース ブロックをこれらのブロックのいずれかに接続する場合は、[Samples per frame] を必要な値に設定します。このモデルでは Bernoulli Binary Generator ブロックの [Samples per frame] パラメーターは、Hamming Encoder ブロックの [Message Length K] パラメーターの倍数でなければなりません。

Display ブロックのラベル付け

ブロックの下に表示されるラベルを変更し、有用な情報を入力することができます。たとえば、Display ブロックの下のラベルを 'Error Rate Display' に変更するには、まずマウスでラベルを選択します。これにより、テキストの周囲にボックスが表示されます。ボックスにテキストへの変更を入力します。

ハミング符号モデルの実行

モデルを実行するには、[シミュレーション]、[実行] を選択します。モデルは 100 の誤りが発生すると終了します。Display ブロックの最上部のウィンドウに表示されるエラー レートはおよそ .001 です。モデルで [Initial seed] パラメーターを変更するか、シミュレーションの実行時間を変えると、結果は若干異なります。

エラー レートがおよそ .001 になることは、次の理由から予想されます。2 つ以上の誤りが長さ 7 のコードワードで発生する確率は次のようになります。

1 – (0.99)⁷ – 7(0.99)⁶(0.01) = 0.002

2 つ以上の誤りを含んだコードワードがランダムに復号化されると、復号化されたメッセージ ワード内のビットのおよそ半分が無効であると予想されます。したがって、ビット エラー レート .001 は妥当な値と言えます。

同じ誤り確率で低いエラー レートを得るには、大きなパラメーターでハミング符号を使用してみてください。このためには、Hamming Encoder および Hamming Decoder ブロック ダイアログ ボックスの [Codeword length] および [Message length] パラメーターを変更します。Bernoulli Binary Generator ブロックおよび Binary Symmetric Channel ブロックのパラメーターも適切に変更する必要があります。

フレーム サイズの表示

モデルの異なる部分のデータ フレームのサイズを表示することができます。[デバッグ] タブで、[情報のオーバーレイ] を展開します。[信号] セクションで、[信号の次元] を選択します。Bernoulli Binary Generator ブロックから出ているラインには [4x1] というラベルが付いています。これは、出力がサイズ 4 の列ベクトルから構成されていることを示します。Hamming Encoder ブロックは [7,4] 符号を使用するため、サイズ 4 のフレームはサイズ 7 のフレームに変換され、その結果、出力は [7x1] となります。

スコープのモデルへの追加

Binary Symmetric Channel ブロックが生成したチャネル誤りを表示するには、Scope ブロックをモデルに追加します。この方法は、モデルが正しく機能しているかどうかを確認する場合に役立ちます。以下の図に示した例は、Scope ブロックをモデルに挿入する場所を示しています。

図 ハミング符号を使用してエラー レートを減らす に示したモデルからこのモデルを作成するには、次の手順に従います。

1. モデル ウィンドウにブロック名を入力し、次のブロックを追加します。

   • Relational Operator (Simulink)

   • Scope (Simulink)

   • Unbuffer の 2 つのコピー

2. Binary Symmetric Channel ブロックをダブルクリックして、そのダイアログ ボックスを開き、[Output error vector] を選択します。これにより、誤りベクトルをもつブロックの 2 番目の出力端子が作成されます。

3. Scope ブロックをダブルクリックして、[表示]、[コンフィギュレーション プロパティ] の下で [入力端子の数] を 2 に設定します。[レイアウト] を選択して、2 つのブロックを垂直に強調表示します。[OK] をクリックします。

4. 前の図に示したようにブロックを接続します。

拡張モデルでのパラメーターの設定

モデルに追加したブロックのパラメーターに次の変更を行います。

• Error Rate Calculation Block – Error Rate Calculation ブロックをダブルクリックし、ブロックのダイアログ ボックスの [Stop simulation] の隣にあるボックスをオフにします。

• Scope Block – Scope (Simulink) ブロックにはチャネル誤りと未補正の誤りが表示されます。ブロックを設定するには、以下のようにします。

  1. Scope ブロックをダブルクリックして、[表示]、[コンフィギュレーション プロパティ] を選択します。

  2. [時間] タブを選択して、[時間範囲] を 5000 に設定します。

  3. [ログ] タブを選択して、[データ点の制限] を 30000 に設定します。

  4. [OK] をクリックします。

  5. スコープが以下のように表示されます。

     

  6. 座標軸を設定するには、次の手順に従います。

     1. 上部のスコープの左側にある縦軸を右クリックします。

     2. コンテキスト メニューで [コンフィギュレーション プロパティ] を選択します。

     3. [Y 軸範囲 (最小)] を -1 に設定します。

     4. [Y 軸範囲 (最大)] を 2 に設定して、[OK] をクリックします。

     5. 下部のスコープの縦軸にも同じ手順を適用します。

     6. スコープ ウィンドウの幅を高さの約 3 倍になるまで広げます。これには、左マウス ボタンを押しながら、ウィンドウの右の境界をクリックし境界を右にドラッグします。

• Relational Operator - ブロックのダイアログ ボックスで [関係演算子] を ~= に設定します。Relational Operator ブロックは Bernoulli Random Generator ブロックからの送信信号と Hamming Decoder ブロックからの受信信号を比較します。2 つの信号が一致すると 0 が出力され、一致しない場合は 1 が出力されます。

スコープによるチャネル誤りの観察

モデルを実行する場合は、スコープに誤りデータが表示されます。5000 のタイム ステップを終了するたびに、スコープは以下の図のように表示されます。この後、スコープは表示されたデータをクリアし、次の 5000 のデータ点を表示します。

上部のスコープは、Binary Symmetric Channel ブロックが生成したチャネル誤りを示します。下部のスコープは、チャネル符号化によって訂正されていない誤りを示します。

スコープを停止するには、モデル ウィンドウの上部のツール バーにある [停止] ボタンをクリックします。

個々の誤りは、スコープをズーム インすることで確認できます。まず、Scope ウィンドウの左上にある真ん中の虫眼鏡ボタンをクリックします。次に、下部のスコープでいずれかのラインをクリックします。これにより、ラインが横方向に拡大されます。横方向のスケールが個々の誤りを検出できるくらいに拡大されるまで、下部のスコープのラインをクリックし続けます。以下の図は、典型的な例を示します。

上部のスコープの真ん中にある幅の広い矩形パルスは 2 つの 1 を表します。1 つのコードワードで発生するこれらの 2 つの誤りは訂正されていません。これは、下部のスコープにある補正されていない誤りからも把握できます。上部のスコープの右側にある幅の狭い矩形パルスは 1 つの誤りを表し、これは訂正されています。

誤りの確認を完了したら、[シミュレーション]、[停止] を選択します。

MATLAB へのデータのエクスポートでは、誤りデータを MATLAB ワークスペースに送信し、詳しく解析する方法について説明しています。

BCH 符号

• BCH 符号に対するワードの表現

• BCH 符号に対するパラメーター

• BCH 符号の作成と復号化

• BCH と RS の誤りのみの復号化のアルゴリズム

BCH 符号に対するワードの表現

[n,k] BCH 符号に対するメッセージは、k 列のバイナリ ガロア体配列でなければなりません。そのメッセージに対応するコードは、n 列のバイナリ ガロア体配列です。これらのガロア体配列の各行は、1 つのワードを表します。

以下の例は、[15, 11] BCH 符号に対するワードの表現方法を示します。

msg = [1 0 0 1 0; 1 0 1 1 1]; % Messages in a Galois array
obj = comm.BCHEncoder;
c1 = step(obj, msg(1,:)');
c2 = step(obj, msg(2,:)');
cbch = [c1 c2].'

出力は以下のようになります。

  Columns 1 through 5

      1            0            0            1            0
      1            0            1            1            1

  Columns 6 through 10

      0            0            1            1            1
      0            0            0            0            1

  Columns 11 through 15

      1            0            1            0            1
      0            1            0            0            1  

BCH 符号に対するパラメーター

BCH 符号は、n と k の特殊な値を使用します。

• コードワード長 n は、ある整数 m > 2 に対して形式 2^m-1 の整数です。

• メッセージ長 k は、n より小さい正の整数です。ただし、n より小さいいくつかの正の整数のみが k に対して有効です。511 までの n の値に対する k の有効な値のリストは、BCH Encoder ブロックのリファレンス ページを参照してください。

BCH 符号の作成と復号化

BCH Encoder System object と BCH Decoder System object は、BCH 符号に対するワードの表現およびBCH 符号に対するパラメーターに説明されているデータを使用して BCH 符号を作成し、復号化します。

トピックは、以下のとおりです。

• 例:BCH 符号化の構文

• MATLAB を使用した BCH 符号の誤りの検出と訂正

例:BCH 符号化の構文.  以下の例は、[15, 5] BCH 符号を使用してデータを符号化および復号化する方法を示します。

n = 15; k = 5; % Codeword length and message length
msg = randi([0 1],4*k,1); % Four random binary messages

% Simplest syntax for encoding
enc = comm.BCHEncoder(n,k);
dec = comm.BCHDecoder(n,k);
c1 = step(enc,msg); % BCH encoding
d1 = step(dec,c1); % BCH decoding

% Check that the decoding worked correctly.
chk = isequal(d1,msg)

% The following code shows how to perform the encoding and decoding
% operations if one chooses to prepend the parity symbols.

% Steps for converting encoded data with appended parity symbols
% to encoded data with prepended parity symbols
c11 = reshape(c1, n, []);
c12 = circshift(c11,n-k);
c1_prepend = c12(:); % BCH encoded data with prepended parity symbols

% Steps for converting encoded data with prepended parity symbols
% to encoded data with appended parity symbols prior to decoding
c21 = reshape(c1_prepend, n, []);
c22 = circshift(c21,k);
c1_append = c22(:); % BCH encoded data with appended parity symbols

% Check that the prepend-to-append conversion worked correctly.
d1_append = step(dec,c1_append);
chk = isequal(msg,d1_append)

出力は以下のようになります。

chk =

     1

MATLAB を使用した BCH 符号の誤りの検出と訂正.  次の例は、誤りのあるコードの復号化結果を示します。この例では、データを符号化し、各コードワードに誤りを加え、BCH Decoder System object を使用して、ノイズを含む符号の復号化を試みます。

n = 15; k = 5; % Codeword length and message length
[gp,t] = bchgenpoly(n,k); % t is error-correction capability.
nw = 4; % Number of words to process
msgw = randi([0 1], nw*k, 1); % Random k-symbol messages
enc = comm.BCHEncoder(n,k,gp);
dec = comm.BCHDecoder(n,k,gp);
c = step(enc, msgw); % Encode the data.
noise = randerr(nw,n,t); % t errors per codeword
noisy = noise';
noisy = noisy(:);
cnoisy = mod(c + noisy,2); % Add noise to the code.
[dc, nerrs] = step(dec, cnoisy); % Decode cnoisy.

% Check that the decoding worked correctly.
chk2 = isequal(dc,msgw)
nerrs % Find out how many errors have been corrected.

ノイズの値の配列はバイナリ値を含むこと、および c が GF(2) のガロア体配列であるために加算演算 c + noise はガロア体 GF(2) 上で行われることに注意してください。

例からの出力は以下のようになります。ans が 0 以外の値である場合、復号化器が誤りを含むコードワードを訂正して元のメッセージを復元できたことを示します。ベクトル nerrs の値は、復号化器が各コードワードにおいて t 個の誤りを訂正したことを示します。

chk2 =

     1


nerrs =

     3
     3
     3
     3

BCH コードワード内での過度のノイズ

前の例では、BCH Decoder System object によってすべての誤りが訂正されました。しかし、各 BCH 符号の誤り訂正能力には限界があります。ノイズが過度である場合の BCH Decoder System object の動作の詳細は、リード・ソロモンコードワード内での過度のノイズにあるリード・ソロモン符号についての同様の説明を参照してください。

BCH と RS の誤りのみの復号化のアルゴリズム

概要.  BCH および RS 符号に使用される誤りのみの復号化アルゴリズムは、以下のステップ ([2]の 5.3.2、5.4、5.6 節) で説明します。

1. 無限次数シンドローム多項式、$$S(z)$$ の最初の 2t 項を計算します。

2. $$S(z)$$ のこれらの 2t 項がすべてゼロに等しい場合、符号誤りはないため訂正は不要となり、復号化アルゴリズムは終了します。

3. $$S(z)$$ に 1 つ以上の非ゼロ項がある場合は、Berlekamp アルゴリズムを使用して誤り位置多項式 Λ(z) を計算します。

4. 誤り評価多項式 $$\Omega \left(z\right)$$ を計算します。

   $$\Lambda \left(z\right)S\left(z\right)=\Omega \left(z\right)\mathrm{mod}{z}^{2t}$$

5. 次の式に従ってコードワードの誤りを修正します。

   $$e_{i_m}=\frac{\Omega ({\alpha }^{-i_m})}{\Lambda \text{'}({\alpha }^{-i_m})}$$

   ここで、$$e_{i_m}$$ はコードワードの $$i_m$$ 番目の位置における誤りの大きさで、m はその符号の誤り訂正能力よりも小さい値、$$\Omega \left(z\right)$$ は誤り量多項式、Λ'(z) は誤り位置多項式 Λ(z) の形式導関数[5]、そして α は符号のガロア体原始元です。

いくつかの手順の詳細は、次の節で説明します。

シンドローム計算.  狭義のコードの場合、$$S(z)$$ の 2t 項は、受け取ったコードワードを 0 ～ 2t-1 の α (体の原始元) の逐次べき乗で評価して計算されます。言い換えると、コードワード $$C(z)$$ とシンドローム多項式 $$S(z)$$ が 1 ベースでインデックスが付けられ、コードワードが $$[c_1{c}_1\mathrm{...}{c}_N]$$ の形式であると仮定した場合、$$S(z)$$ の各項 $$S_i$$は以下のようになります。

$$S_i={\displaystyle \sum _{i=1}^N{c}_i}{\alpha }^{N-1-i}$$

誤り位置多項式の計算.  誤り位置多項式 Λ(z) は Berlekamp アルゴリズムを使用して見つけます。このアルゴリズムの詳細な説明は[2]に記載されていますが、アルゴリズムの要約を以下に示します。

次の変数を定義します。

変数	説明
n	Iterator 変数
k	Iterator 変数
L	$$S(z)$$ の最初の 2t 項を生成するために使用するフィードバック レジスタの長さ
D(z)	訂正多項式
d	誤差

次の図は、Λ(z) を見つけるために使用する反復手法 (Berlekamp アルゴリズム) を示します。

誤り評価多項式の計算.  誤り評価多項式 $$\Omega \left(z\right)$$ は単純に、Λ(z) と $$S(z)$$ の畳み込みです。

リード・ソロモン符号

• リード・ソロモン符号のワードの表現

• リード・ソロモン符号のパラメーター

• リード・ソロモン符号の作成と復号化

• 生成多項式の決定

• 短縮、パンクチャ、および消去を使用するリード・ソロモンの例

リード・ソロモン符号のワードの表現

このツールボックスは、ビットの代わりに m ビットのシンボルを使用するリード・ソロモン符号をサポートします。[n,k] リード・ソロモン符号に対するメッセージは、体 GF(2^m) の k 列のガロア体配列でなければなりません。各配列エントリは、0 から 2^m-1 の整数でなければなりません。そのメッセージに対応するコードは、GF(2^m) の n 列のガロア体配列です。コードワード長 n は、3 から 2^m-1 の値でなければなりません。

メモ

ガロア体配列とその作成方法の詳細は、ガロア体の元の表現または関数 gf のリファレンス ページを参照してください。

以下の例は、[7,3] リード・ソロモン符号に対するワードの表現方法を示します。

n = 7; k = 3; % Codeword length and message length
m = 3; % Number of bits in each symbol
msg = [1 6 4; 0 4 3]; % Message is a Galois array.
obj = comm.RSEncoder(n, k);
c1 = step(obj, msg(1,:)');
c2 = step(obj, msg(2,:)');
c = [c1 c2].'

出力は以下のようになります。

C =

     1     6     4     4     3     6     3
     0     4     3     3     7     4     7

リード・ソロモン符号のパラメーター

この節では、リード・ソロモン符号に関連する整数について説明し、生成多項式の求め方を説明します。

使用可能な整数パラメーターの値.  次の表は、このツールボックスでサポートされるリード・ソロモン符号に関連する正の整数値の意味とそれらが取りうる値をまとめています。値 n と k は、このツールボックスでのリード・ソロモン関数の入力パラメーターです。

シンボル	平均	値または範囲
m	シンボルあたりのビット数	3 から 16 の整数
n	コードワードごとのシンボル数	3 から 2m-1 の整数
k	メッセージごとのシンボル数	n よりも小さい正の整数 (n-k は偶数)
t	符号の誤り訂正能力	(n-k)/2

生成多項式.  関数 rsgenpoly は、リード・ソロモン符号に対する生成多項式を作成します。rsgenpoly は、多項式の係数を変数の "降べき" の順にリストするガロア行ベクトルを使用して生成多項式を表します。各シンボルに m ビットがある場合は、ガロア行ベクトルは体 GF(2^m) に属します。たとえば、次のコマンド

r = rsgenpoly(15,13)

r = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)

Array elements =

     1     6     8

このコマンドにより、[15,13] リード・ソロモン符号に対する生成多項式は X² + (A² + A)X + (A³) となります。ここで、A は GF(16) に対する既定の原始多項式の根です。

生成多項式の代数表現

rsgenpoly が生成する生成多項式の形式は、(X - A^b)(X - A^b+1)...(X - A^b+2t-1) です。ここで、b は整数、A はガロア体に対する原始多項式の根、t は (n-k)/2 です。b の既定値は 1 です。rsgenpoly の出力は、要素の乗算と X のべき乗の収集の結果です。以下の例は、b = 1 を使用して、[15,13] リード・ソロモン符号の場合にこの式をチェックします。

n = 15;
a = gf(2,log2(n+1)); % Root of primitive polynomial
f1 = [1 a]; f2 = [1 a^2]; % Factors that form generator polynomial
f = conv(f1,f2) % Generator polynomial, same as r above.

リード・ソロモン符号の作成と復号化

RS Encoder System object および RS Decoder System object は、リード・ソロモン符号のワードの表現とリード・ソロモン符号のパラメーターで説明したデータを使用してリード・ソロモン符号を作成し、復号化します。

この節では、RS Encoder System object および RS Decoder System object の使用方法を説明します。トピックは、以下のとおりです。

• MATLAB でのリード・ソロモン符号化の構文

• MATLAB を使用したリード・ソロモン符号の誤りの検出と訂正

• リード・ソロモンコードワード内での過度のノイズ

• 短縮リード・ソロモン符号の作成

MATLAB でのリード・ソロモン符号化の構文.  以下の例は、[15,13] リード・ソロモン符号を使用してデータを符号化および復号化する複数の方法を示します。この例から、以下のタスクを実行できることがわかります。

• 異なる生成多項式を作成するために rsgenpoly を使用してコードの生成多項式を変更する

• gf の入力引数を使用して、シンボルを含むガロア体の原始多項式を変更する

• 末尾 (既定) または先頭を選択して、コードワード内のパリティ シンボルの位置を変更する

この例では、RS Encoder System object と RS Decoder System object の対応する構文が、最初の入力引数を除き同じ入力引数を使用することも示します。

m = 4; % Number of bits in each symbol
n = 2^m-1; k = 13; % Codeword length and message length
msg = randi([0 m-1],4*k,1); % Four random integer messages

% Simplest syntax for encoding
hEnc = comm.RSEncoder(n,k);
hDec = comm.RSDecoder(n,k);
c1 = step(hEnc, msg);
d1 = step(hDec, c1);


% Vary the generator polynomial for the code.
release(hEnc), release(hDec)
hEnc.GeneratorPolynomialSource = 'Property';
hDec.GeneratorPolynomialSource = 'Property';
hEnc.GeneratorPolynomial       = rsgenpoly(n,k,19,2);
hDec.GeneratorPolynomial       = rsgenpoly(n,k,19,2);
c2 = step(hEnc, msg);
d2 = step(hDec, c2);

% Vary the primitive polynomial for GF(16).
release(hEnc), release(hDec)
hEnc.PrimitivePolynomialSource = 'Property';
hDec.PrimitivePolynomialSource = 'Property';
hEnc.GeneratorPolynomialSource = 'Auto';
hDec.GeneratorPolynomialSource = 'Auto';
hEnc.PrimitivePolynomial       = [1 1 0 0 1];
hDec.PrimitivePolynomial	   = [1 1 0 0 1];
c3 = step(hEnc, msg);
d3 = step(hDec, c3);

% Check that the decoding worked correctly.
chk = isequal(d1,msg) & isequal(d2,msg) & isequal(d3,msg)

% The following code shows how to perform the encoding and decoding
% operations if one chooses to prepend the parity symbols.

% Steps for converting encoded data with appended parity symbols
% to encoded data with prepended parity symbols
c31 = reshape(c3, n, []);
c32 = circshift(c31,n-k);
c3_prepend = c32(:); % RS encoded data with prepended parity symbols

% Steps for converting encoded data with prepended parity symbols
% to encoded data with appended parity symbols prior to decoding
c34 = reshape(c3_prepend, n, []);
c35 = circshift(c34,k);
c3_append = c35(:); % RS encoded data with appended parity symbols

% Check that the prepend-to-append conversion worked correctly.
d3_append = step(hDec,c3_append);
chk = isequal(msg,d3_append)

出力は以下のようになります。

chk =

     1

MATLAB を使用したリード・ソロモン符号の誤りの検出と訂正.  以下の例は、誤りのあるコードの復号化結果を示します。この例では、データを符号化し、各コードワードに誤りを加え、RS Decoder System object を使用して、ノイズを含む符号の復号化を試みます。

m = 3; % Number of bits per symbol
n = 2^m-1; k = 3; % Codeword length and message length
t = (n-k)/2; % Error-correction capability of the code
nw = 4; % Number of words to process
msgw = randi([0 n],nw*k,1); % Random k-symbol messages
hEnc = comm.RSEncoder(n,k);
hDec = comm.RSDecoder(n,k);
c = step(hEnc, msgw); % Encode the data.
noise = (1+randi([0 n-1],nw,n)).*randerr(nw,n,t); % t errors per codeword
noisy = noise';
noisy = noisy(:);
cnoisy = gf(c,m) + noisy; % Add noise to the code under gf(m) arithmetic.
[dc nerrs] = step(hDec, cnoisy.x); % Decode the noisy code.
% Check that the decoding worked correctly.
isequal(dc,msgw)
nerrs % Find out how many errors hDec corrected.

ノイズ値の配列には、1 から 2^m の整数が含まれます。c が GF(2^m) 内のガロア体配列であるため、加算演算 c + noise はガロア体 GF(2^m) 上で行われます。

例からの出力は以下のようになります。ans が 0 以外の値である場合、復号化器が誤りを含むコードワードを訂正して元のメッセージを復元できたことを示します。ベクトル nerrs の値は、復号化器が各コードワードにおいて t 個の誤りを訂正したことを示します。

ans =

     1

nerrs =

     2
     2
     2
     2

リード・ソロモンコードワード内での過度のノイズ.  前の例では、RS Encoder System object によってすべての誤りが訂正されましたが。しかし、各リード・ソロモン符号の誤り訂正能力には限界があります。ノイズが大きいために、正しいコードワードから誤りを含むコードワードまでのハミング距離が非常に大きい場合、以下のいずれかになります。

• 誤りを含むコードワードが、正しいコードワード "以外" の有効なコードワードの近似になる。復号化器は、他のコードワードに対応するメッセージを出力します。

• 誤りを含むコードワードは、正常な復号化のコードワードとの距離が近くない。この状況は、"復号化失敗" と呼ばれます。復号化器は、誤りを含むコードワードからパリティ位置のシンボルを削除し、残りのシンボルを出力します。

両方の場合とも、復号化器は誤ったメッセージを出力します。ただし、RS Decoder System object は 2 番目の出力で値 -1 も返すので、復号化失敗がいつ発生するのかを知ることができます。

コードワードにノイズが多すぎて復号化に失敗する場合について調べるには、前の例を変更して noise を次のように定義します。

noise = (1+randi([0 n-1],nw,n)).*randerr(nw,n,t+1); % t+1 errors/row

短縮リード・ソロモン符号の作成.  リード・ソロモン符号化器は、整数 m に対して 2^m-1 のコードワード長を使用します。短縮リード・ソロモン符号のコードワード長は 2^m-1 ではありません。短縮 [n,k] リード・ソロモン符号は、暗黙的に [n₁,k₁] 符号化器を使用します。ここで、

• n₁ = 2^m - 1、m はシンボルあたりのビット数です。

• k₁ = k + (n₁ - n)

RS Encoder System object では、非短縮符号用と同じ構文で短縮符号がサポートされます。短縮符号を使用することを明示的に示す必要はありません。

hEnc = comm.RSEncoder(7,5);
ordinarycode = step(hEnc,[1 1 1 1 1]');
hEnc = comm.RSEncoder(5,3);
shortenedcode = step(hEnc,[1 1 1 ]');

RS Encoder System object による短縮符号の作成方法

短縮符号を作成する際、RS Encoder System object では以下のステップを実行します。

• 各メッセージの前に 0 を付加する

• 有効なコードワード長と目的の誤り訂正能力をもつリード・ソロモン符号化器を使用して、0 を付加されたメッセージを符号化する

• 各コードワードの非パリティ シンボルから余分な 0 を削除する

次の例はこのプロセスを説明します。

n = 12; k = 8; % Lengths for the shortened code
m = ceil(log2(n+1)); % Number of bits per symbol
msg = randi([0 2^m-1],3*k,1); % Random array of 3 k-symbol words
hEnc = comm.RSEncoder(n,k);
code = step(hEnc, msg); % Create a shortened code.

% Do the shortening manually, just to show how it works.
n_pad = 2^m-1; % Codeword length in the actual encoder
k_pad = k+(n_pad-n); % Messageword length in the actual encoder
hEnc = comm.RSEncoder(n_pad,k_pad);
mw = reshape(msg,k,[]); % Each column vector represents a messageword
msg_pad = [zeros(n_pad-n,3); mw]; % Prepend zeros to each word.
msg_pad = msg_pad(:);
code_pad = step(hEnc,msg_pad); % Encode padded words.
cw = reshape(code_pad,2^m-1,[]); % Each column vector represents a codeword
code_eqv = cw(n_pad-n+1:n_pad,:); % Remove extra zeros.
code_eqv = code_eqv(:);
ck = isequal(code_eqv,code); % Returns true (1).

生成多項式の決定

巡回、BCH、リード・ソロモン符号に対する生成多項式を求めるには、それぞれ関数 cyclpoly、bchgenpoly、または rsgenpoly を使用します。次のコマンドを見てみましょう。

genpolyCyclic = cyclpoly(15,5) % 1+X^5+X^10
genpolyBCH = bchgenpoly(15,5)  % x^10+x^8+x^5+x^4+x^2+x+1
genpolyRS = rsgenpoly(15,5)

これらのコマンドは、異なるタイプのブロック符号に対する生成多項式を求めます。出力は以下のようになります。

genpolyCyclic =

     1     0     0     0     0     1     0     0     0     0     1

 
genpolyBCH = GF(2) array. 
 
Array elements = 
 
     1     0     1     0     0     1     1     0     1     1     1

 
genpolyRS = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)
 
Array elements = 
 
     1     4     8    10    12     9     4     2    12     2     7

これらの出力の形式は、次のように変わります。

• cyclpoly は、多項式の係数を変数の "昇べき" の順にリストする整数の行ベクトルを使用して、生成多項式を表します。

• bchgenpoly と rsgenpoly は、多項式の係数を変数の "降べき" の順にリストするガロア行ベクトルを使用して、生成多項式を表します。

• rsgenpoly は、二元体 GF(2) 以外のガロア体の係数を使用します。これらの係数の意味の詳細は、整数をガロア体にどのように対応づけるかとガロア体上の多項式を参照してください。

生成多項式の非一意性.  メッセージ長とコードワード長のペアによって、生成多項式が一意に決定されない場合があります。上記の例の関数の構文には、指定する特定の制約を満たす生成多項式を取り出すためのオプションも含まれています。構文のオプションの詳細は、関数のリファレンス ページを参照してください。

生成多項式の代数表現.  bchgenpoly と rsgenpoly によって生成される生成多項式の形式は、(X - A^b)(X - A^b+1)...(X - A^b+2t-1) です。ここで、A は適切なガロア体に対する原始元で、b と t は整数です。この式の詳細は、関数のリファレンス ページを参照してください。

短縮、パンクチャ、および消去を使用するリード・ソロモンの例

このセクションでは、短縮、パンクチャ、および消去を使用した代表的なリード・ソロモン符号化例を、ますます複雑になる誤り訂正を含めて作成します。

短縮とパンクチャを使用した符号化器例.  次の図は、短縮とパンクチャを使用した (7,3) リード・ソロモン符号化器の代表的な例を示しています。

この図では、メッセージ ソースにより I₁I₂ で指定される 2 つの情報シンボルが出力されます (BCH の例では、シンボルはバイナリ ビットにすぎません)。この符号は短縮 (7,3) 符号であるため、情報シンボルの前にゼロを追加しなければなりません。これにより、0I₁I₂ という 3 つのシンボルから構成されるメッセージが生成されます。変更されたメッセージ シーケンスは、RS で符号化され、追加された情報ゼロはそのあと削除されます。その結果 I₁I₂P₁P₂P₃P₄ が生成されます (この例では、パリティ ビットはコードワードの末尾にあります)。

パンクチャ操作は、パンクチャ ベクトルによって制御されます。ここでは、このパンクチャ ベクトルは 1011 です。パンクチャ ベクトル内では、1 はシンボルが保持され、0 はシンボルが破棄されたことを意味します。この例では、パンクチャ操作により 2 番目のパリティ シンボルが削除され、I₁I₂P₁P₃P₄ という最終的なベクトルが生成されます。

短縮とパンクチャを使用した復号化器例.  次の図は、短縮コードワードおよびパンクチャコードワードでの RS 符号化器の動作を示しています。

このケースは、短縮とパンクチャを使用した RS 符号化器の図に示した符号化器の動作に対応します。前の図に示したとおり、符号化器は (5,2) コードワードを受信します。これは (7,3) コードワードから 1 シンボル短縮され、さらにその 1 シンボルはパンクチャされているためです。

最初のステップとして、復号化器は、コードワードの第 2 のパリティ位置に E で指定された消去を追加します。これは、パンクチャ ベクトル 1011 に対応します。前の図に示したとおり、ゼロを追加することは短縮を意味します。1 回の消去は、4 つの消去を訂正できる符号の消去訂正機能を超えません。復号化操作により、3 つのシンボルで構成されるメッセージ DI₁I₂ が生成されます。前の図のように最初のシンボルは切り捨てられるので、最終出力は I₁I₂ になります。

短縮、パンクチャ、および消去を使用した符号化器例.  次の図は、パンクチャされ、短縮コードワードに対して動作しながら、受信機によって生成された消去を生成する復号化器の様子を示しています。

この図では、復調器は符号化器が送信した I₁I₂P₁P₃P₄ ベクトルを受信します。復調器は、受信した 5 つのシンボルのうち 2 つは、信頼できないので消去されることを宣言するため、シンボル 2 と 5 は消去と見なされます。外部ソースによって提供された 01001 ベクトルは、これらの消去を示しています。消去ベクトル内では、1 はシンボルが消去シンボルで置き換えられること、0 はシンボルが変更なしで渡されることを意味します。

復号化器のブロックは、コードワードと消去ベクトルを受信し、ベクトル 01001 で示される消去を実行します。消去ベクトル内では、1 はシンボルが消去シンボルで置き換えられること、0 はシンボルが変更なしで渡されることを意味します。結果のコードワード ベクトルは、I₁EP₁P₃E になります。ここで、E は消去シンボルです。

コードワードは、符号化操作で使用したパンクチャ ベクトル (1011 など) に基づきデパンクチャされます。したがって、消去シンボルが P₁ と P₃ の間に挿入され、I₁EP₁EP₃E というコードワード ベクトルが生成されます。

復号化の直前に、情報ベクトルの冒頭にゼロを追加することは短縮を意味します。結果のベクトルは、0I₁EP₁EP₃E になるため、(7,3) コードワードは Berlekamp アルゴリズムに送られます。

このコードワードは復号化され、3 つのシンボルで構成される DI₁I₂ (ここで、D はダミー シンボルを示します) というメッセージが生成されます。最後に、メッセージ ベクトルから D シンボルを削除することは、短縮を意味し、元の I₁I₂ ベクトルが生成されます。

詳細は、Simulink での消失、パンクチャ、および短縮を使用したリード・ソロモン符号化の例を参照してください。

LDPC 符号

低密度パリティ チェック (LDPC) コードは、以下を伴う線形の誤り制御符号です。

• スパース パリティ チェック行列

• シャノン限界に近いパフォーマンスを達成できる長いブロック長 (LDPC Encoder および LDPC Decoder を参照)

Communications Toolbox は、Simulink ブロックと MATLAB オブジェクトを使用して LDPC 符号を実行します。

復号化処理は反復して行われます。反復数が小さすぎると、アルゴリズムが収束しないことがあります。モデルの適切な値を見つけるために、多くの反復を行って実験する必要があることもあります。復号化アルゴリズムの詳細は、復号化アルゴリズムを参照してください。

他のコーデックと違い、復号化器は対数尤度比 (LLR) を必要とするので、LDPC 符号化器の出力に LDPC 復号化器を直接接続することはできません。従って、LLR を計算するために復調器を使用できます。

さらに、他の復号化器と違い、LDPC 復号化器の出力が一部のパリティ チェックを満たさない可能性もあります。

ガロア体の計算

"ガロア体" は、有限個の要素をもつ代数体です。2^m 個の要素をもつガロア体は、誤り制御符号化で利用され、GF(2^m) と記されます。この節では、2^m 個の要素をもつ体の取り扱いについて説明します。ここで、m は 1 から 16 までの整数です。この節には、以下の小節があります。

• ガロア体の用語

• ガロア体の元の表現

• ガロア体の演算

• ガロア体の論理演算

• ガロア体の行列操作

• ガロア体の線形代数

• ガロア体での信号処理操作

• ガロア体上の多項式

• ガロア変数の操作

• 既定でない原始多項式と計算速度

• ガロア体の参考文献

奇数個の要素をもつガロア体を使用する必要がある場合は、奇数個の元をもつガロア体を参照してください。

ガロア体の要素からなる配列を扱う特定の関数の詳細は、MATLAB または Communications Toolbox ソフトウェア用ドキュメンテーションのオンライン リファレンス ページを参照してください。

メモ

ガロア体オブジェクトは copy メソッドをサポートしません。

ガロア体への一般化が簡単に記述できる MATLAB 関数についてのリファレンス ページは、MATLAB ドキュメンテーションの項目と重複するため、このマニュアルにはありません。

ガロア体の用語

本書ではガロア体の説明について、文献と整合性のない用語をいくつか利用します。ここで利用される定義は、van Lint[4]に記述されています。

• GF(2^m) の "原始元" は、GF(2^m) の非ゼロ元の巡回生成を行います。これは、この体のすべての非ゼロ元がこの原始元の整数乗として表されることを意味します。

• GF(2^m) の "原始多項式" は、GF(2^m) の原始元の最小多項式です。これは、GF(2^m) の根としてある原始元をもつ最小の非ゼロ次数のバイナリ係数多項式です。そのため、原始多項式は次数 m をもち、既約です。

この定義は、原始元が対応する原始多項式の根であることを意味しています。

ガロア体の元の表現

• この節の概要

• ガロア体配列の作成

• 例:ガロア体変数の作成

• 例:GF(8) の元の表現

• 整数をガロア体にどのように対応づけるか

• 例:原始元の表現

• 原始多項式と元の表現

この節の概要.  この節では、ガロア体の元を表す MATLAB 式である "ガロア体配列" の作成方法について説明します。この節では、MATLAB 技術計算ソフトウェアが表現で使う数値をどのように解釈するかについても説明し、例も示します。

ガロア体配列の作成.  ガロア体 GF (2^m) のデータから作業を始めるために、体に関する重要な情報とデータを関連付けることによって、コンテキストを設定しなければなりません。関数 gf は、この関連付けを行い、MATLAB 上でガロア体配列を作成します。この関数は、入力として以下を受け取ります。

• ガロア体データ x。これは、要素が 0 から 2^m-1 の間の整数である MATLAB 配列です。

• ("オプション") x が体 GF(2^m) 上にあることを示す整数 m。m の有効な値は 1 と 16 の間の値です。既定値は 1 です。これは、体が GF(2) であることを意味します。

• ("オプション") x 内の表現で GF(2^m) のどの原始多項式を利用しているかを示す正の整数。この入力引数を省略する場合は、gf は GF(2^m) に対する既定の原始多項式を使います。この引数についての詳細は、原始多項式と元の表現を参照してください。

関数 gf の出力は、MATLAB が、整数の配列ではなくガロア体配列として認識する変数です。結果として、変数を操作すると、MATLAB は指定したガロア体内で動作します。たとえば、関数 log をガロア体配列に適用する場合、MATLAB は、実数または複素数の体ではなく、ガロア体内で対数を計算します。

MATLAB がガロア体配列を暗黙的に作成する場合

ガロア体配列の演算の中には、複数の引数が必須のものがあります。1 つの引数にはガロア体配列を指定し、もう 1 つには通常の MATLAB 配列を指定する場合、MATLAB は両方を同じ体のガロア体配列と解釈します。つまり、通常の MATLAB 配列に対して関数 gf を暗黙的に呼び出します。この暗黙的な呼び出しでは、関数 gf への参照がいくらか省略されるため、構文が簡略化されます。簡略化の例については、例:加算と減算を参照してください。

例:ガロア体変数の作成.  下記のコードは、元が体 GF(4) にある行ベクトルを作成し、行自身を加算します。

x = 0:3; % A row vector containing integers
m = 2; % Work in the field GF(2^2), or, GF(4).
a = gf(x,m) % Create a Galois array in GF(2^m).

b = a + a % Add a to itself, creating b.

出力は以下のようになります。

a = GF(2^2) array. Primitive polynomial = D^2+D+1 (7 decimal)

Array elements =

     0     1     2     3


b = GF(2^2) array. Primitive polynomial = D^2+D+1 (7 decimal)

Array elements =

     0     0     0     0

出力は、名前が a、b というガロア体配列の値を示します。各出力セクションは、次を示します。

• GF(2^2) = GF(4) という変数を含む体

• 体に対する原始多項式。この場合、GF(4) に対するツールボックスの既定の原始多項式です。

• 変数を含むガロア体の値からなる配列。特に、a の配列要素は、ベクトル x の要素であり、b の配列要素は GF(4) の 4 つのゼロです。

b を作成するコマンドは、変数 a をガロア体配列として定義し、通常の + 演算子を利用することによって a 自身を加算する方法を示します。MATLAB は、体 GF(4) においてベクトル化された加算を行います。出力は、次を示します。

• a と比較すると、b は同じ体にあり、同じ原始多項式を利用します。和 b を定義する際に体を示す必要はありません。これは、MATLAB が加算の定義 a の情報を記憶しているためです。

• b の配列要素は、ゼロです。これは、"標数 2" のガロア体内の任意の値同士の和がゼロであるためです。この結果は、無限の整数の体での加算を表す和 x + x とは異なります。

例:GF(8) の元の表現.  ガロア体配列内の配列要素が何を意味するかを示すために、下記の表は、GF(8) の元を整数および原始元 A の多項式としてリストします。この表は、次のようなガロア体配列を解釈するのに役立ちます。

gf8 = gf([0:7],3); % Galois vector in GF(2^3)

整数表現	バイナリ表現	GF(8) の元
0	000	0
1	001	1
2	010	A
3	011	A + 1
4	100	A2
5	101	A2 + 1
6	110	A2 + A
7	111	A2 + A + 1

整数をガロア体にどのように対応づけるか.  上記の例の GF(8) において、この節では、より一般的なガロア体配列内の配列要素の解釈を説明します。体 GF(2^m) は、2^m 個の元をもち、このツールボックスでは 0, 1, 2,..., 2^m-1 というラベルを付けます。これらの整数ラベルは、体の原始元を含む多項式表現によって、ガロア体の元に対応します。より具体的には、0 と 2^m-1 の間の整数は、m ビットの 2 進表現をもちます。2 進表現のビットを多項式の係数として使うと (最下位ビットは定数項)、次数が最大で m-1 であるバイナリ多項式になります。GF(2^m) の原始元においてバイナリ多項式を評価すると、体の元になります。

逆に GF(2^m) の任意の元は、次数が最大 m-1 のバイナリ多項式として表され、体の原始元で評価されます。多項式の m 組 (ベクトル表現) の係数は、0 から 2^m の整数のバイナリ表現に対応します。

下記は、2 進形式で表された整数 X とガロア体の元の対応をシンボリックに示しています。各 b_k はゼロまたは 1 で、A は原始元です。

$$\begin{array}{c}X=b_{m-1}\cdot 2^{m-1}+\cdots +b_2\cdot 4+b_1\cdot 2+b_0\\ \leftrightarrow b_{m-1}\cdot A^{m-1}+\cdots +b_2\cdot A^2+b_1\cdot A+b_0\end{array}$$

例:原始元の表現.  下記のコードは、体 GF(2⁴) 上の原始元を表す変数 alph を定義します。

m = 4; % Or choose any positive integer value of m.
alph = gf(2,m) % Primitive element in GF(2^m)

出力は以下のようになります。

alph = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)

Array elements =

     2

ガロア体配列 alph は、以下の対応により、原始元を表します。

• gf 構文で指定された整数 2

• 2 の 2 進表現 10 (または 4 ビットを利用した 0010)

• 多項式 A + 0。ここで A は、この体の原始元です (または、A の 4 つの低次のべき乗を使った 0A³ + 0A² + A + 0)

原始多項式と元の表現.  この節では、ガロア体配列の作成に基づき、ガロア体配列の作成時に独自仕様の原始多項式を指定する方法を説明します。トピックは、以下のとおりです。

既定でない原始多項式を使って多くの計算を実行する場合は、既定でない原始多項式と計算速度を参照してください。

原始多項式の指定

整数をガロア体にどのように対応づけるかでは、体の原始多項式の根である原始元を説明しています。関数 gf を利用してガロア体配列を作成する際に、別の原始多項式を明示的に指定しない限り、関数は配列内の整数をその体に固有の既定の原始多項式について解釈します。既定の原始多項式のリストは、関数 gf のリファレンス ページにあります。

ガロア体配列の作成時に独自仕様の原始多項式を指定するには、

c = gf(5,4,25) % 25 indicates the primitive polynomial for GF(16).

を使用します。

c1= gf(5,4); % Use default primitive polynomial for GF(16).

は、使用しません。この場合 25 である追加入力引数は、整数をガロア体にどのように対応づけるか で説明した表現と同じ方法で、体 GF(2^m) の原始多項式を指定します。この場合、整数 25 は、2 進表現 11001 に対応し、多項式 D⁴ + D³ + 1 に対応します。

メモ

原始多項式の指定時に、入力引数は、不要な先頭のゼロを含まずに、正確に m+1 ビットを使った 2 進表現でなければなりません。言い換えると、GF(2^m) に対する原始多項式は、常に次数 m です。

入力引数を利用して原始多項式を指定する際には、出力は整数値と多項式表現を示すことによって、選択を反映します。

d = gf([1 2 3],4,25)

d = GF(2^4) array. Primitive polynomial = D^4+D^3+1 (25 decimal)

Array elements =

     1     2     3

メモ

ガロア体配列を定義した後で、MATLAB が配列要素を解釈する原始多項式を変更することはできません。

原始多項式を求める

GF(2^m) に対する原始多項式を求めるために関数 primpoly を、また、多項式が GF(2^m) に対して原始多項式であるかどうかを決定するために、関数 isprimitive を利用することができます。次のコードにより実証します。

m = 4;
defaultprimpoly = primpoly(m) % Default primitive poly for GF(16)
allprimpolys = primpoly(m,'all') % All primitive polys for GF(16)
i1 = isprimitive(25) % Can 25 be the prim_poly input in gf(...)?
i2 = isprimitive(21) % Can 21 be the prim_poly input in gf(...)?

出力は以下のようになります。

Primitive polynomial(s) =

D^4+D^1+1

defaultprimpoly =

    19

Primitive polynomial(s) =

D^4+D^1+1
D^4+D^3+1

allprimpolys =

    19
    25

i1 =

     1

i2 =

     0

数値結果への既定でない原始多項式の影響

ほとんどの体には、体の要素の表現のための原始多項式について複数の選択肢があります。関数 gf を使うとき、原始多項式を変更すると、配列要素の解釈が変わり、そのためガロア体配列へのその後の演算の結果も変わります。たとえば、原始元の指数形式は、原始多項式が体の元の表現にどのように影響を与えるかをわかりやすくします。

a11 = gf(2,3); % Use default primitive polynomial of 11.
a13 = gf(2,3,13); % Use D^3+D^2+1 as the primitive polynomial.
z = a13.^3 + a13.^2 + 1 % 0 because a13 satisfies the equation
nz = a11.^3 + a11.^2 + 1 % Nonzero. a11 does not satisfy equation.

下記の出力は、原始多項式が整数表現 13 をもつとき、ガロア体配列はある式を満たすことを示します。一方、原始多項式が整数表現 11 をもつときには、ガロア体配列は式を満たしません。

z = GF(2^3) array. Primitive polynomial = D^3+D^2+1 (13 decimal)

Array elements =

     0


nz = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal)

Array elements =

     6

この例を行ったときの出力は、ルックアップ テーブルに関する警告を含む場合もあります。これは、13 の既定でない原始多項式に関する計算を最適化するために関数 gftable を利用しなかった場合には正常です。

ガロア体の演算

• この節の概要

• 例:加算と減算

• 例:乗算

• 例:除算

• 例:べき乗

• 例:要素単位の対数

この節の概要.  下記の表にリストされた通常の MATLAB 演算子を使って、ガロア体配列に対する算術演算を実行することができます。ガロア体配列の組について演算を行うときは、配列は両方とも同じガロア体になければなりません。

操作	演算子
加算	+
減算	-
要素単位の乗算	.*
行列乗算	*
要素単位の左除算	./
要素単位の右除算	.\
行列の左除算	/
行列の右除算	\
要素ごとのべき乗	.^
要素単位の対数	log()
正方ガロア行列のスカラー整数による指数形式	^

ガロア体上の多項式の乗算と除算については、多項式の加算と減算を参照してください。

例:加算と減算.  下記のコードは 2 つのガロア体配列を加算し、GF(8) に対する加算テーブルを作成します。加算は、通常の + 演算子を利用します。下記のコードは、GF(8) の元に 1 を加算した結果を求めるために addtb 配列にインデックスを付ける方法も示します。

m = 3;
e = repmat([0:2^m-1],2^m,1);
f = gf(e,m); % Create a Galois array.
addtb = f + f' % Add f to its own matrix transpose.

addone = addtb(2,:); % Assign 2nd row to the Galois vector addone.

出力は以下のようになります。

addtb = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal)

Array elements =

     0     1     2     3     4     5     6     7
     1     0     3     2     5     4     7     6
     2     3     0     1     6     7     4     5
     3     2     1     0     7     6     5     4
     4     5     6     7     0     1     2     3
     5     4     7     6     1     0     3     2
     6     7     4     5     2     3     0     1
     7     6     5     4     3     2     1     0

この加算テーブルの解釈の例として、addtb 配列の (7,4) エントリは、gf(6,3) プラス gf(3,3) が gf(5,3) に等しいことを示します。同様に、元 A²+A プラス元 A+1 は、元 A²+1 に等しくなります。この等価性は、6 の 2進表現が 110、3 の 2進表現が 011、5 の 2進表現が 101 であることから生じます。

+ を - で置き換えることによって得られる減算テーブルは、addtb と同じです。これは、減算と加算は "標数 2" の体では同じ演算であるためです。実際に、addtb の主対角の 0 は、GF(8) に対してこの事実を示しています。

構文の簡略化

下記のコードは、スカラー拡張と通常の MATLAB 配列からガロア体配列を暗黙的に作成する方法を示します。ガロア体配列 h と h1 は同一ですが、h の作成は簡単な構文を使います。

g = gf(ones(2,3),4); % Create a Galois array explicitly.
h = g + 5; % Add gf(5,4) to each element of g.
h1 = g + gf(5*ones(2,3),4) % Same as h.

出力は以下のようになります。

h1 = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)

Array elements =

     4     4     4
     4     4     4

1+5 はガロア体では 4 として出力されることに注目します。5 は多項式表現 A²+1 を表し、GF(16) の 1+(A²+1) は A² であるので、これは真になります。さらに、多項式表現 A² を表す整数は 4 です。

例:乗算.  下記の例は、ガロア体配列の個々の元を .* 演算子を使って乗算します。その後で、* 演算子を使って行列乗算を行います。要素単位の乗算は、サイズがその入力と一致する配列を生成します。一方、行列乗算は行ベクトルと列ベクトルの行列の積であるため、ガロア スカラーを生成します。

m = 5;
row1 = gf([1:2:9],m); row2 = gf([2:2:10],m);
col = row2'; % Transpose to create a column array.
ep = row1 .* row2; % Elementwise product.
mp = row1 * col; % Matrix product.

GF(8) に対する乗算テーブル

別の例として、下記のコードは、行列乗算を使って 2 つのガロア ベクトルを乗算します。結果は、GF(8) に対する乗算テーブルです。

m = 3;
els = gf([0:2^m-1]',m);
multb = els * els' % Multiply els by its own matrix transpose.

出力は以下のようになります。

multb = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal)

Array elements =

     0     0     0     0     0     0     0     0
     0     1     2     3     4     5     6     7
     0     2     4     6     3     1     7     5
     0     3     6     5     7     4     1     2
     0     4     3     7     6     2     5     1
     0     5     1     4     2     7     3     6
     0     6     7     1     5     3     2     4
     0     7     5     2     1     6     4     3

例:除算.  下記の例は、個々の元および配列の乗法的逆元を計算することによって、ガロア体での 4つの除算演算子を示します。inv を利用、あるいは -1 の指数を利用して逆数を計算することもできます。

要素ごとの除算

この例では、./ および .\ 演算子を使ってガロア体配列の個々の要素でそれぞれ 1 を除算します。これらの 2つの演算子は、入力引数の順序のみが異なります。各商ベクトルは、体の非ゼロ元の乗法的逆元のリストです。この例では、MATLAB は、計算の前にスカラー 1 をサイズ nz に拡張します。あるいは、同じサイズの 2 つの配列を引数として使うことができます。

m = 5;
nz = gf([1:2^m-1],m); % Nonzero elements of the field
inv1 = 1 ./ nz; % Divide 1 by each element.
inv2 = nz .\ 1; % Obtain same result using .\ operator.

行列の除算

この例では、/ および \ 演算を使って正方ガロア体配列 mat で単位配列を除算します。各商行列は、mat の乗法的逆元です。\ を使った等価な演算で転置演算子 (') がどのように現れるかに注目してください。正方行列に対しては、転置演算のシーケンスは不要ですが、非正方行列に対しては必要です。

m = 5;
mat = gf([1 2 3; 4 5 6; 7 8 9],m);
minv1 = eye(3) / mat; % Compute matrix inverse.
minv2 = (mat' \ eye(3)')'; % Obtain same result using \ operator.

例:べき乗.  下記の例は、ガロア体配列の整数乗の計算方法を示します。ガロア体配列に対して行列のべき乗を行うには、底として正方ガロア体配列を使い、指数として (ガロアでなく) 通常の整数スカラーを使わなければなりません。

要素ごとのべき乗

この例は、ガロア体の原始元 A のべき乗を計算します。次に、これらの別々に計算されたべき乗を使って、A で既定の原始多項式を評価します。0 という答えは、A が原始多項式の根であることを示します。.^ 演算子は、配列の元を別々にべき乗します。

m = 3;
av = gf(2*ones(1,m+1),m); % Row containing primitive element
expa = av .^ [0:m]; % Raise element to different powers.
evp = expa(4)+expa(2)+expa(1) % Evaluate D^3 + D + 1.

出力は以下のようになります。

evp = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal)

Array elements =

     0

行列のべき乗

この例は、行列を -1 乗することで正方行列の逆を計算します。さらに、正方行列を 2 乗と -2 乗します。

m = 5;
mat = gf([1 2 3; 4 5 6; 7 8 9],m);
minvs = mat ^ (-1); % Matrix inverse
matsq = mat^2; % Same as mat * mat
matinvssq = mat^(-2); % Same as minvs * minvs

例:要素単位の対数.  下記のコードは、ガロア体配列の要素の対数を計算します。出力は、GF(8) の "非ゼロ元" を原始元のべき乗として表す方法を示します。体の元ゼロの対数は未定義です。

gf8_nonzero = gf([1:7],3); % Vector of nonzero elements of GF(8)
expformat = log(gf8_nonzero) % Logarithm of each element

出力は以下のようになります。

expformat =

     0     1     3     2     6     4     5

出力の解釈方法の例として、この例の各ベクトルの最後のエントリを考えます。GF(8) の元 gf(7,3) が以下のいずれかで表すことができると推定できます。

• expformat の最後の元を使った、A⁵。

• 7 のバイナリ表現として 111 を使った、A²+A+1。詳細については、例:GF(8) の元の表現を参照してください。

ガロア体の論理演算

• この節の概要

• 等価性のテスト

• 非ゼロ値のテスト

この節の概要.  ガロア体配列に論理テストを適用し、logical 配列を得ることができます。重要なテスト タイプは、2 つのガロア体配列の等価性を調べることと、ガロア体配列内の非ゼロ値を調べることです。

等価性のテスト.  同じサイズをもつ 2 つのガロア体配列の対応する要素を比較するために、演算子 == と ~= を利用します。結果は、logical 配列で、各要素は対応する要素ごとの比較が真または偽であることを示します。同じ演算子を利用してスカラーとガロア体配列を比較する場合は、MATLAB 技術計算ソフトウェアはスカラーと配列の各要素を比較し、同じサイズの論理配列を生成します。

m = 5; r1 = gf([1:3],m); r2 = 1 ./ r1;
lg1 = (r1 .* r2 == [1 1 1]) % Does each element equal one?
lg2 = (r1 .* r2 == 1) % Same as above, using scalar expansion
lg3 = (r1 ~= r2) % Does each element differ from its inverse?

出力は以下のようになります。

lg1 =

     1     1     1


lg2 =

     1     1     1


lg3 =

     0     1     1

isequal と == の比較

配列全体を比較し、logical 配列ではなく logical "スカラー" の結果を得るために、組み込み関数 isequal を利用することができます。しかし、isequal は比較に対して厳格な規則を使い、以下を比較する場合には 0 (false) を出力します。

• ガロア体配列と通常の MATLAB 配列 (基となる配列要素の値が一致していても)

• スカラーと非スカラー配列 (配列内のすべての要素がスカラーと一致しても)

下記の例は、== と isequal の違いを示します。

m = 5; r1 = gf([1:3],m); r2 = 1 ./ r1;
lg4 = isequal(r1 .* r2, [1 1 1]); % False
lg5 = isequal(r1 .* r2, gf(1,m)); % False
lg6 = isequal(r1 .* r2, gf([1 1 1],m)); % True

非ゼロ値のテスト.  ガロア ベクトル内、または複数行をもつガロア体配列の列の非ゼロ値を調べるには、関数 any または関数 all を使います。これらの 2 つの関数は、基となる配列要素のみを考慮し、元がどのガロア体に含まれるかに関する情報を無視すること以外は、通常の MATLAB 関数 any および all と同様に機能します。例は、以下のとおりです。

m = 3; randels = gf(randi([0 2^m-1],6,1),m);
if all(randels) % If all elements are invertible
    invels = randels .\ 1; % Compute inverses of elements.
else
    disp('At least one element was not invertible.');
end
alph = gf(2,4);
poly = 1 + alph + alph^3;
if any(poly) % If poly contains a nonzero value
    disp('alph is not a root of 1 + D + D^3.');
end
code = [0:4 4 0; 3:7 4 5]
if all(code,2) % Is each row entirely nonzero?
    disp('Both codewords are entirely nonzero.');
else
    disp('At least one codeword contains a zero.');
end

ガロア体の行列操作

• ガロア体配列の基本操作

• ガロア体配列に関する基本情報

ガロア体配列の基本操作.  ガロア体配列の基本的な配列操作を次の表に示します。これらの演算の機能は、同じ構文をもつ MATLAB 演算と同じです。

操作	構文
場合によっては、明示的なインデックスをもつベクトルではなくコロン演算子を使った配列へのインデックス付け	a(vector) または a(vector,vector1)。vector および/または vector1 は、ベクトルではなく ":" になります。
配列転置	a'
行列の連結	[a,b] または [a;b]
指定した対角要素をもつ配列の作成	diag(vector) または diag(vector,k)
対角要素の抽出	diag(a) または diag(a,k)
下三角部分の抽出	tril(a) または tril(a,k)
上三角部分の抽出	triu(a) または triu(a,k)
配列の型の変更	reshape(a,k1,k2)

下記のコードはこれらの構文を利用します。

m = 4; a = gf([0:15],m);
a(1:2) = [13 13]; % Replace some elements of the vector a.
b = reshape(a,2,8); % Create 2-by-8 matrix.
c = [b([1 1 2],1:3); a(4:6)]; % Create 4-by-3 matrix.
d = [c, a(1:4)']; % Create 4-by-4 matrix.
dvec = diag(d); % Extract main diagonal of d.
dmat = diag(a(5:9)); % Create 5-by-5 diagonal matrix
dtril = tril(d); % Extract upper and lower triangular
dtriu = triu(d); % parts of d.

ガロア体配列に関する基本情報.  関数 length および関数 size を利用して、ガロア ベクトルの長さやガロア体配列のサイズを決定することができます。ガロア体配列に対する機能は、関数 size および関数 length の出力引数がガロア体配列ではなく常に整数であること以外は、通常の配列に対する MATLAB 演算と同じです。下記のコードは、これらの関数の使用法を示します。

m = 4; e = gf([0:5],m); f = reshape(e,2,3);
lne = length(e); % Vector length of e
szf = size(f); % Size of f, returned as a two-element row
[nr,nc] = size(f); % Size of f, returned as two scalars
nc2 = size(f,2); % Another way to compute number of columns

非ゼロ要素の位置

ガロア体配列から決定したい別のタイプの情報は、非ゼロ要素の位置です。通常の MATLAB 配列に対しては、関数 find を使います。しかし、ガロア体配列に対しては、以下のように find と ~= 演算子を組み合わせて利用します。

x = [0 1 2 1 0 2]; m = 2; g = gf(x,m);
nzx = find(x); % Find nonzero values in the ordinary array x.
nzg = find(g~=0); % Find nonzero values in the Galois array g.

ガロア体の線形代数

• 逆行列と行列式の計算

• ランクの計算

• 正方行列の分解

• 線形方程式の解

逆行列と行列式の計算.  正方ガロア体配列を反転させるには、関数 inv を使います。関連する関数は det で、ガロア体配列の行列式を計算します。関数 inv と関数 det は、両方とも複素数の体ではなくガロア体で計算を行うこと以外は、通常の MATLAB のバージョンのように機能します。

メモ

ガロア体配列は、行列式が正確にゼロである場合にのみ特異です。実数や複素数配列の場合のように、丸め誤差を考慮する必要はありません。

下記のコードは、逆行列と行列式の計算を示します。

m = 4;
randommatrix = gf(randi([0 2^m-1],4,4),m);
gfid = gf(eye(4),m);
if det(randommatrix) ~= 0
    invmatrix = inv(randommatrix);
    check1 = invmatrix * randommatrix;
    check2 = randommatrix * invmatrix;
    if (isequal(check1,gfid) & isequal(check2,gfid))
        disp('inv found the correct matrix inverse.');
    end
else
    disp('The matrix is not invertible.');
end

この例の出力は、ランダムに生成された行列が非特異か、あるいは特異かに応じて、以下の 2 つのメッセージのいずれかになります。

inv found the correct matrix inverse.
The matrix is not invertible.

ランクの計算.  ガロア体配列のランクを計算するには、関数 rank を使います。入力引数を 1 つだけ指定した場合には、通常の MATLAB 関数 rank と同様に機能します。下記の例は、正方および非正方ガロア体配列のランクを求める方法を示します。

m = 3;
asquare = gf([4 7 6; 4 6 5; 0 6 1],m);
r1 = rank(asquare);
anonsquare = gf([4 7 6 3; 4 6 5 1; 0 6 1 1],m);
r2 = rank(anonsquare);
[r1 r2]

出力は以下のようになります。

ans =

     2     3

r1 と r2 の値は、asquare がフル ランクでないことと、anonsquare がフル ランクであることを示します。

正方行列の分解.  正方ガロア体配列 (またはその並べ替え) を下三角ガロア体配列と上三角ガロア体配列の積として表すには、関数 lu を使います。この関数は、1 入力引数を受け取り、2 つまたは 3 つの出力引数を生成します。同じ構文を指定した場合は、通常の MATLAB 関数 lu と同様に機能します。下記の例は、lu を利用した分解方法を示します。

tofactor = gf([6 5 7 6; 5 6 2 5; 0 1 7 7; 1 0 5 1],3);
[L,U]=lu(tofactor); % lu with two output arguments
c1 = isequal(L*U, tofactor) % True
tofactor2 = gf([1 2 3 4;1 2 3 0;2 5 2 1; 0 5 0 0],3);
[L2,U2,P] = lu(tofactor2); % lu with three output arguments
c2 = isequal(L2*U2, P*tofactor2) % True

線形方程式の解.  ガロア体で線形方程式の固有の解を求めるには、ガロア体配列に対して \ または / 演算子を使います。次の表は、A と B がガロア体配列とあらかじめ定義されていると仮定し、各演算子が扱う式を示します。

演算子	線形方程式	構文	\ を使った等価な構文
バックスラッシュ (\)	A * x = B	x = A \ B	該当なし
スラッシュ (/)	x * A = B	x = B / A	x = (A'\B')'

表の構文の結果は、ガロア体配列 A の特性により異なります。

• A が正方で非特異の場合は、出力 x は線形方程式の一意的な解です。

• A が正方で特異の場合は、表の構文はエラーになります。

• A が正方でない場合は、MATLAB は、特解を求めようとします。A'*A または A*A' が特異配列である場合、あるいは A が過決定システムを表す行列 (行数が列数より多い行列) である場合は、試みは失敗します。

メモ

エラー メッセージは、線形方程式が解をもたないことを必ずも指摘しません。問題を言い換えることにより、解を求めることができる場合があります。たとえば、gf([1 2; 0 0],3) \ gf([1; 0],3) はエラーになりますが、数学的に等価な gf([1 2],3) \ gf([1],3) はエラーになりません。最初の構文は、gf([1 2; 0 0],3) が特異正方行列であるため失敗します。

例:線形方程式の解

下記の例は、ガロア体について線形方程式の固有の解を求める方法を示します。

m = 4;
A = gf(magic(3),m); % Square nonsingular matrix
Awide=[A, 2*A(:,3)]; % 3-by-4 matrix with redundancy on the right
Atall = Awide'; % 4-by-3 matrix with redundancy at the bottom
B = gf([0:2]',m);
C = [B; 2*B(3)];
D = [B; B(3)+1];
thesolution = A \ B; % Solution of A * x = B
thesolution2 = B' / A; % Solution of x * A = B'
ck1 = all(A * thesolution == B) % Check validity of solutions.
ck2 = all(thesolution2 * A == B')
% Awide * x = B has infinitely many solutions. Find one.
onesolution = Awide \ B;
ck3 = all(Awide * onesolution == B) % Check validity of solution.
% Atall * x = C has a solution.
asolution = Atall \ C;
ck4 = all(Atall * asolution == C) % Check validity of solution.
% Atall * x = D has no solution.
notasolution = Atall \ D;
ck5 = all(Atall * notasolution == D) % It is not a valid solution.

この例の出力は、偽 (0) である ck5 以外は、妥当性のチェックはすべて真 (1) であることを示します。

ガロア体での信号処理操作

• この節の概要

• Filtering

• 畳み込み

• 離散フーリエ変換

この節の概要.  フィルター処理、畳み込み、離散フーリエ変換のような信号処理操作をガロア体配列に対して行うことができます。

この節は、これらの操作の実行方法を説明します。

通常の実数ベクトルの対応する操作に関するその他の情報は、Signal Processing Toolbox™ ドキュメンテーションに記載されています。

Filtering.  ガロア ベクトルをフィルター処理するには、関数 filter を使います。入力引数を 3 つだけ指定した場合には、通常の MATLAB 関数 filter と同様に機能します。

下記のコードと図は、GF(2) 上の特定のフィルターのインパルス応答を示します。

m = 1; % Work in GF(2).
b = gf([1 0 0 1 0 1 0 1],m); % Numerator
a = gf([1 0 1 1],m); % Denominator
x = gf([1,zeros(1,19)],m);
y = filter(b,a,x); % Filter x.
figure; stem(y.x); % Create stem plot.
axis([0 20 -.1 1.1])

畳み込み.  Communications Toolbox ソフトウェアは、ガロア ベクトルの組を畳み込みする 2 つの等価な方法を提供します。

• 多項式の乗算と除算 で説明した関数 conv を利用します。これは、2 つのベクトルの畳み込みが、係数がベクトルのエントリである 2 つの多項式の乗算と等価であるため機能します。

• 関数 convmtx を使ってベクトルの畳み込み行列を計算した後で、その行列と別のベクトルを乗算します。これは、2 つのベクトルの畳み込みが、片方のベクトルをもう一方のベクトルでフィルター処理することと等価であるためです。この等価性により、デジタル フィルターを畳み込み行列として表すことができ、適切な長さの任意のガロア ベクトルを乗算することができます。

ヒント

大規模なガロア ベクトルの畳み込みを行う必要がある場合、畳み込み行列の乗算は、conv の利用よりも高速な場合があります。

例

GF(4) のベクトル b に対し畳み込み行列を計算します。デジタル フィルターの分子係数を表し、その後、2 つの等価な、ガロア体上の x による b の畳み込みの方法を示します。

m = 2; b = gf([1 2 3]',m);
n = 3; x = gf(randi([0 2^m-1],n,1),m);
C = convmtx(b,n); % Compute convolution matrix.
v1 = conv(b,x); % Use conv to convolve b with x
v2 = C*x; % Use C to convolve b with x.

離散フーリエ変換.  離散フーリエ変換は、デジタル信号処理の重要なツールです。このツールボックスは、離散フーリエ変換の処理に役立つ以下のツールを提供します。

• fft。ガロア ベクトルを変換

• ifft。ガロア ベクトルについて逆離散フーリエ変換を行います。

• dftmtx。ガロア ベクトルについて離散フーリエ変換またはその逆を行うためのガロア体配列を出力します。

すべての場合で、変換されるベクトルは、体 GF(2^m) の長さ 2^m-1 のガロア ベクトルでなければなりません。以下の例では、これらの関数の使用法を示します。関数 isequal を使用して、y は y1 と同等で、z が z1 と同等で、z が x と同等であることを確認できます。

m = 4;
x = gf(randi([0 2^m-1],2^m-1,1),m); % A vector to transform
alph = gf(2,m);
dm = dftmtx(alph);
idm = dftmtx(1/alph);
y = dm*x; % Transform x using the result of dftmtx.
y1 = fft(x); % Transform x using fft.
z = idm*y; % Recover x using the result of dftmtx(1/alph).
z1 = ifft(y1); % Recover x using ifft.

ヒント

変換したいベクトルが (同じ体に) 多くある場合は、fft を何回も使うよりも、dftmtx を 1 回、行列乗算を複数回行うほうが高速となる場合があります。

ガロア体上の多項式

• この節の概要

• 多項式の加算と減算

• 多項式の乗算と除算

• 多項式の評価

• 多項式の根

• バイナリ多項式の根

• 最小多項式

この節の概要.  ガロア ベクトルを使って、不定量 x で多項式を、ガロア体でその係数を表すことができます。多項式の係数を x の降べき順にベクトルに並べることによって、表現を作成します。たとえば、次のベクトルを例に説明します。

gf([2 1 0 3],4)

は、多項式 Ax³ + 1x² + 0x + (A+1) を表します。ここで、

• A は、体 GF(2⁴) の原始元です。

• x は、多項式の不定量です。

このようなガロア ベクトルを使って演算の実行、多項式の評価、多項式の根を求めることができます。ガロア体の元の最小多項式を求めることもできます。

多項式の加算と減算.  多項式を加算および減算するには、多項式を表す長さの等しいガロア ベクトルに対して通常の + および - 演算子を使います。片方の多項式がもう一方よりも低次である場合は、2 つのベクトルが同じ長さとなるように、短い方のベクトルの先頭にゼロを付加しなければなりません。下記の例は、1 次と 2 次の多項式を加える方法を示します。

lin = gf([4 2],3); % A^2 x + A, which is linear in x
linpadded = gf([0 4 2],3); % The same polynomial, zero-padded
quadr = gf([1 4 2],3); % x^2 + A^2 x + A, which is quadratic in x
% Can't do lin + quadr because they have different vector lengths.
sumpoly = [0, lin] + quadr; % Sum of the two polynomials
sumpoly2 = linpadded + quadr; % The same sum

多項式の乗算と除算.  多項式を乗算および除算するには、多項式を表すガロア ベクトルに対して関数 conv と関数 deconv を利用します。多項式の乗算と除算は、ベクトルの畳み込みと逆畳み込みと等価です。関数 deconv は、2 つの多項式の商と剰余多項式を出力します。例は、以下のとおりです。

m = 4;
apoly = gf([4 5 3],m); % A^2 x^2 + (A^2 + 1) x + (A + 1)
bpoly = gf([1 1],m); % x + 1
xpoly = gf([1 0],m); % x
% Product is A^2 x^3 + x^2 + (A^2 + A) x + (A + 1).
cpoly = conv(apoly,bpoly);
[a2,remd] = deconv(cpoly,bpoly); % a2==apoly. remd is zero.
[otherpol,remd2] = deconv(cpoly,xpoly); % remd is nonzero.

ガロア体の演算における乗算と除算の演算は、多項式ではなく、要素または行列を乗算します。

多項式の評価.  ガロア体の元について多項式を評価するには、関数 polyval を使います。入力引数を 2 つだけ指定した場合には、通常の MATLAB 関数 polyval と同様に機能します。下記の例は、体のいくつかの元で多項式を評価し、体の .^ と .* を使って結果をチェックします。

m = 4;
apoly = gf([4 5 3],m); % A^2 x^2 + (A^2 + 1) x + (A + 1)
x0 = gf([0 1 2],m); % Points at which to evaluate the polynomial
y = polyval(apoly,x0)

a = gf(2,m); % Primitive element of the field, corresponding to A.
y2 = a.^2.*x0.^2 + (a.^2+1).*x0 + (a+1) % Check the result.

出力は以下のようになります。

y = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)

Array elements =

     3     2    10


y2 = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)

Array elements =

     3     2    10

y の最初の要素は、0 で多項式を評価するので、多項式の定数項 3 を出力します。

多項式の根.  ガロア体において多項式の根を求めるには、多項式を表すガロア ベクトルに対して関数 roots を使います。この関数はガロア ベクトルが存在するのと同じ体の根を求めます。roots からの出力ベクトルにエントリが表示される回数は、多項式の根の多重度になります。

メモ

ガロア ベクトルが GF(2^m) にある場合は、それが表す多項式は、拡大体 GF((2^m)^k) に根をもつ場合があります。しかし、roots はそれらの付加的な根は求めないか、あるいは存在を示しません。

下記の例は、GF(8) 上で 3 次多項式の根を求めます。

p = 3; m = 2;
field = gftuple([-1:p^m-2]',m,p); % List of all elements of GF(9)
% Use default primitive polynomial here.
polynomial = [1 0 1 1]; % 1 + x^2 + x^3
rts =gfroots(polynomial,m,p) % Find roots in exponential format
% Check that each one is actually a root.
for ii = 1:3
   root = rts(ii);
   rootsquared = gfmul(root,root,field);
   rootcubed = gfmul(root,rootsquared,field);
   answer(ii)= gfadd(gfadd(0,rootsquared,field),rootcubed,field);
   % Recall that 1 is really alpha to the zero power.
   % If answer = -Inf, then the variable root represents
   % a root of the polynomial.
end
answer

バイナリ多項式の根.  バイナリ係数をもつ特殊な多項式の場合では、拡大体に存在する根を求めることは簡単です。これは、元 0 と 1 が標数 2 のすべての体で同じ明白な表現をもつためです。拡大体においてバイナリ多項式の根を求めるには、関数 roots を、配列要素が多項式のバイナリ係数である拡大体内のガロア ベクトルに適用します。

下記の例は、さまざまな体においてバイナリ多項式の根を探します。

gf2poly = gf([1 1 1],1); % x^2 + x + 1 in GF(2)
noroots = roots(gf2poly); % No roots in the ground field, GF(2)
gf4poly = gf([1 1 1],2); % x^2 + x + 1 in GF(4)
roots4 = roots(gf4poly); % The roots are A and A+1, in GF(4).
gf16poly = gf([1 1 1],4); % x^2 + x + 1 in GF(16)
roots16 = roots(gf16poly); % Roots in GF(16)
checkanswer4 = polyval(gf4poly,roots4); % Zero vector
checkanswer16 = polyval(gf16poly,roots16); % Zero vector

多項式の根は GF(2) に存在しないので、noroots は空配列です。しかし、多項式の根は GF(4) と GF(16) に存在するため、roots4 と roots16 は空ではありません。

roots4 と roots16 は互いに等しくないことに注意してください。これらは、以下の点が異なります。

• roots4 は GF(4) 配列で、roots16 は GF(16) 配列です。MATLAB は、ガロア体配列の基となる体を追っています。

• roots4 と roots16 の配列要素は、異なる原始多項式に関する表現を使うために異なっています。たとえば、2 (原始元を表す) は、GF(4) に対する既定の原始多項式が gf4poly が表す多項式と同じであるため、ベクトル roots4 の元です。一方、2 は、GF(16) の原始元が gf16poly が表す多項式の根ではないため、roots16 の元ではありません。

最小多項式.  GF(2^m) の元の最小多項式は、元を GF(2^m) の根としてもつ最小次数が非ゼロのバイナリ係数多項式です。元または元の列ベクトルの最小多項式を求めるには、関数 minpol を使います。

下記のコードは、gf(6,4) の最小多項式が D² + D + 1 であることを求め、gf(6,4) が実際に体 GF(16) の多項式の根にあることを検証します。

m = 4;
e = gf(6,4);
em = minpol(e) % Find minimal polynomial of e. em is in GF(2).

emr = roots(gf([0 0 1 1 1],m)) % Roots of D^2+D+1 in GF(2^m)

出力は以下のようになります。

em = GF(2) array.

Array elements =

     0     0     1     1     1


emr = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)

Array elements =

     6
     7

ガロア体のどの元が同じ最小多項式を共有するかを求めるには、関数 cosets を使います。

ガロア変数の操作

• この節の概要

• 変数がガロア体配列であるかどうかを決定

• ガロア体配列から情報を抽出

• ガロア体配列変数に付加した体の拡大サフィックスの使用

この節の概要.  この節では、ガロア体配列と通常の MATLAB 配列間のガロア変数の操作や情報の伝送のための手法を説明します。

メモ

これらの手法は、ガロア体配列を処理する MATLAB ファイル関数を作成する場合に、特に該当します。このタイプの使用例として、コマンド ウィンドウで edit gf/conv と入力し、エディター ウィンドウでコードの最初の数行を調べてください。

変数がガロア体配列であるかどうかを決定.  変数が通常の MATLAB 配列ではなくガロア体配列であるかどうかを調べるには、関数 isa を使います。説明は、以下のとおりです。

mlvar = eye(3);
gfvar = gf(mlvar,3);
no = isa(mlvar,'gf'); % False because mlvar is not a Galois array
yes = isa(gfvar,'gf'); % True because gfvar is a Galois array

ガロア体配列から情報を抽出.  配列要素、体の次数、原始多項式をガロア体配列である変数から抽出するためには、変数名にサフィックスを付加します。次の表は、変数名に依存しないサフィックスを示します。

情報	サフィックス	出力値
配列の要素	.x	ガロア体配列からのデータ値を含む uint16 型の MATLAB 配列
体の次数	.m	ガロア体配列が GF(2^m) にあることを示す double 整数型。
原始多項式	.prim_poly	原始多項式を表す uint32 整数型。表現は、整数をガロア体にどのように対応づけるかでの説明と同じです。

メモ

出力値が整数データ型で、後の操作のために double に変換したい場合は、関数 double を使います。

ガロア体配列変数に付加した体の拡大サフィックスの使用

体の拡大サフィックスを使用して、ガロア体配列から情報を抽出します。

配列の要素 (.x)

ガロア体配列を double に変換します。

a = gf([1,0])

 
a = GF(2) array. 
 
Array elements = 
 
   1   0

b = double(a.x) % a.x is in uint16

b = 1×2

     1     0

体の次数 (.m)

e がそれ自身の最小多項式を解くことを確認します。多項式 (emp.x) のバイナリ係数のベクトルを使用して、体の次数の拡大体 (.m) のガロア体配列として empr を作成します。

e = gf(6,4);                % An element of GF(16)
emp = minpol(e);            % Minimal polynomial is in GF(2)
empr = roots(gf(emp.x,e.m)) % Find roots of emp in GF(16)

 
empr = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)
 
Array elements = 
 
   6
   7

原始多項式 (.prim_poly)

出力ベクトルに 2 が含まれていることを確認して、原始元 gf(2,m) が実際に体に対する原始多項式の根であることを確認します。体に対する原始多項式を取得し、適切なビット数をもつバイナリ ベクトル表現に変換します。

primpoly_int = double(e.prim_poly);
mval = e.m;
primpoly_vect = gf(int2bit(primpoly_int,mval+1)',mval);
containstwo = roots(primpoly_vect)

 
containstwo = GF(2^4) array. Primitive polynomial = D^4+D+1 (19 decimal)
 
Array elements = 
 
   2
   3
   4
   5

既定でない原始多項式と計算速度

原始多項式と元の表現では、選択した原始多項式に関してガロア体の元を表す方法を説明しました。この節では、既定の原始多項式以外の原始多項式を使うガロア体配列に関する計算の高速化の方法について説明します。そのような計算を多く行う場合にこの手法が推奨されます。

高速化のメカニズムは、特定の計算の反復実行を回避するために一部の計算関数が使用するデータ ファイル userGftable.mat です。体の次数 (m) と原始多項式 (prim_poly) の組み合わせに利用するには、以下のようにします。

1. MATLAB アプリケーションで書き込み権限をもつフォルダーに移動します。関数 cd または現在のフォルダー機能を使用すると移動できます。

2. m および prim_poly をワークスペース変数として定義します。次に例を示します。

   m = 3; prim_poly = 13; % Examples of valid values
   

3. 関数 gftable を呼び出します。

   gftable(m,prim_poly); % If you previously defined m and prim_poly
   

関数は、現在の作業フォルダー内で userGftable.mat を変更または作成して、体の次数と原始多項式の組み合わせに関連するデータを含めます。関数 gftable を呼び出す時間を最初に与えると、m および prim_poly の値を使用するその後の計算は高速になります。

メモ

関数 gftable を呼び出した後で現在の作業ディレクトリを変更する場合は、userGftable.mat を MATLAB パス上に配置して MATLAB が確認できるようにする必要があります。これを行うには、addpath コマンドを使用して userGftable.mat を含むディレクトリを MATLAB パスの前に配置します。パス上に userGftable.mat のコピーが複数ある場合は、which('userGftable.mat','-all') を使用してコピーの場所と MATLAB が使っているコピーを確認します。

gftable がどの程度計算速度を向上させたかを調べるには、計算を関数 tic と関数 toc で囲みます。例については、gftable のリファレンス ページを参照してください。

ガロア体の参考文献

[1] Blahut, Richard E., Theory and Practice of Error Control Codes, Reading, MA, Addison-Wesley, 1983, p. 105.

[2] Lang, Serge, Algebra, Third Edition, Reading, MA, Addison-Wesley, 1993.

[3] Lin, Shu, and Daniel J. Costello, Jr., Error Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ, Prentice-Hall, 1983.

[4] van Lint, J. H., Introduction to Coding Theory, New York, Springer-Verlag, 1982.

[5] Wicker, Stephen B., Error Control Systems for Digital Communication and Storage, Upper Saddle River, NJ, Prentice Hall, 1995.

奇数個の元をもつガロア体

"ガロア体" は p^m 個の元をもつ代数体です。ここで、p は素数で、m は正の整数です。この節では、p が "奇素数" のときのガロア体の取り扱いについて説明します。偶数個の元をもつガロア体の取り扱いについては、ガロア体の計算を参照してください。この節には、以下の小節があります。

• ガロア体の用語

• ガロア体の元の表現

• 既定の原始多項式

• 元の形式の変換と簡略化

• ガロア体の演算

• 素体上の多項式

• その他のガロア体関数

• ガロア体の参考文献

ガロア体の用語

この節では、p は奇素数で m は正の整数です。

また、本書では文献と整合性のない用語をいくつか利用します。ここで利用される定義は、van Lint[5]に記述されています。

• GF(p^m) の "原始元" は、GF(p^m) の非ゼロ元の巡回生成を行います。これは、この体のすべての非ゼロ元がこの原始元の整数乗として表されることを意味します。原始元は、この節では A と呼ばれます。

• GF(p^m) の "原始多項式" は、GF(p^m) の原始元の最小多項式です。結果として、次数 m をもち既約です。

ガロア体の元の表現

• この節の概要

• 指数形式

• 多項式形式

• ガロア体のすべての元のリスト

• 表現の非一意性

この節の概要.  この節では、本ツールボックスの指数形式および多項式形式を使ってガロア体の元を表す方法を説明します。ガロア体のすべての元をリストする方法も示します。これは、関数の中には入力引数としてそのようなリストを使うものがあるためです。最後に、ガロア体の元の表現の非一意性を説明します。

GF(p) の元は、0 から p-1 の整数を使って表すことができます。

m が少なくとも 2 である場合、GF(p^m) は拡大体と呼ばれます。整数単独では GF(p^m) の元を直接表すことはできません。MATLAB 技術計算ソフトウェアは、GF(p^m) の元を表すときに 2 つの主要な表記法、指数形式と多項式形式を使用します。

メモ

指数形式と多項式形式は両方共、GF(p^m) の特定の原始元 A の選択に関連します。

指数形式.  この形式は、GF(p^m) のすべての非ゼロ元が 0 から p^m -2 の整数 c に対して A^c として表すことができるという特性を利用します。ガロア体の理論は、GF(p^m) のすべての非ゼロ元が q = p^m のとき式 x^q-1 = 1 を満たすことを示すので、高次の指数は必要ありません。

指数形式の利用を以下の表に示します。

GF(pm) の元	元の MATLAB 表現
0	-Inf
A0 = 1	0
A1	1
...	...
Aq-2 ここで q = pm	q-2

-Inf はゼロ元の標準の指数表現ですが、すべての負の整数は、指数形式で "入力" 引数として使用されると -Inf と等価になります。この等価性は役に立ちます。たとえば、既定の原始多項式の最後のコードの簡潔な行を参照してください。

メモ

指数形式としてすべての負の整数と -Inf が等価であることは、たとえば、-1 は A の乗法的逆元である A^-1 を "表さない" ことを意味します。-1 はこの体のゼロ元を表します。

多項式形式.  多項式形式は、GF(p^m) のすべての元が、0 から m-1 の指数と GF(p) の係数によって、A の多項式として表すことができる特性を利用します。多項式形式では、元

A(1) + A(2) A + A(3) A² + ... + A(m) A^m-1

は、MATLAB では次のベクトルで表されます。

[A(1) A(2) A(3) ... A(m)]

メモ

本ツールボックスのガロア体関数は、係数を変数の "昇べき順" に示すベクトルとして多項式を表します。これは、他の関数 MATLAB が使用する順序とは逆です。

ガロア体のすべての元のリスト.  本ツールボックスのガロア体関数の中には、拡大体 GF(p^m) のすべての元のリストを引数として必要とするものがあります。これは、再度 GF(p^m) の特定の原始元 A に関連します。元のリストに対する適切なフォーマットは、体の各元に対して 1 つずつ、p^m 行をもつ行列のフォーマットです。行列は m 列で、上記の多項式形式に示されている多項式形式の A のべき乗の各係数について 1 列です。1 行目は、GF(p^m) のゼロの元に対応するため、ゼロのみを含みます。k が 2 から p^m の間である場合は、k 行目は元 A^k-2 の多項式形式を指定します。

A の最小多項式は、A のより低階のべき乗で A^m を表す方法を示すので、この行列の計算に役立ちます。たとえば、以下の表は、GF(3²) の元をリストします。ここで、A は、原始多項式 2 + 2x + x² の根です。この多項式を使って、表の中央の列の計算を行うとき、

A² = -2 - 2A = 1 + A

という置換を繰り返し使用できます。

GF(9) の元

指数形式	多項式形式	元の MATLAB 行列の行
A-Inf	0	0 0
A0	1	1 0
A1	A	0 1
A2	1+A	1 1
A3	A + A2 = A + 1 + A = 1 + 2A	1 2
A4	A + 2A2 = A + 2 + 2A = 2	2 0
A5	2A	0 2
A6	2A2 = 2 + 2A	2 2
A7	2A + 2A2 = 2A + 2 + 2A = 2 + A	2 1

例

上記の表の 3 列目に示される行をもつ行列を自動生成するためには、下記のコードを利用します。

p = 3; m = 2;
% Use the primitive polynomial 2 + 2x + x^2 for GF(9).
prim_poly = [2 2 1];
field = gftuple([-1:p^m-2]',prim_poly,p);

関数 gftuple は、元の形式の変換と簡略化で詳しく説明します。

表現の非一意性.  体は、複数の原始元をもちます。2 つの原始元が異なる最小多項式をもつ場合は、対応する元の行列は、異なる順序の行をもちます。2 つの原始元が同じ最小多項式を共有する場合は、体の元の行列は同じです。

メモ

ガロア体関数の入出力が、"ある" 原始多項式の選択に依存することがわかっている限り、どんな原始元でも利用することができます。通常は、与えられたスクリプトまたは関数内で、同じ原始多項式を利用するのが最適です。

元の表現が一意でない他の場合は、ガロア体の元が満たす式から生じます。たとえば、GF(9) の 8 の指数形式は、GF(9) で A⁸ = 1 = A⁰ であるので、0 の指数形式と同じです。別の例として、GF(9) の元 の表の前に説明した置換により、多項式形式 [0 0 1] が多項式形式 [1 1] と同じであることが示されます。

既定の原始多項式

本ツールボックスは、各拡大体に対する "既定の" 原始多項式を提供します。この多項式は、関数 gfprimdf を使って得ることができます。次のコマンド

prim_poly = gfprimdf(m,p); % If m and p are already defined

は、GF(p^m) に対する既定の最小多項式の標準の行ベクトル表現を生成します。

たとえば、下記のコマンドは、GF(9) に対する既定の原始多項式が、ガロア体のすべての元のリストで使われる多項式 "ではなく"、2 + x + x² であることを示します。

poly1=gfprimdf(2,3);

poly1 =

     2     1     1

既定の原始多項式を利用して GF(p^m) の元のリストを生成するには、以下のコマンドを使います。

field = gftuple([-1:p^m-2]',m,p);

元の形式の変換と簡略化

• 最も簡単な多項式形式に変換

• 例:ガロア体の元のリストの生成

• 最も簡単な指数形式への変換

最も簡単な多項式形式に変換.  関数 gftuple は、元の指数表現または多項表現を与えると、GF(p^m) の元の最も簡単な多項式表現を生成します。これは、他の関数で要求される GF(p^m) の元のリストの生成に役立ちます。

gftuple を利用するには、3 つの引数が必要です。GF(p^m) の元を表すもの、出力の計算時に MATLAB 技術計算ソフトウェアが使用する原始多項式を示すもの、および素数 p です。下記の表は、最初の 2 つの引数がさまざまな形式であるときに、関数 gftuple がどのように動作するかを示します。

初めの 2 つの入力の形式に依存する gftuple の動作

元の指定方法	原始多項式を表す方法	gftuple が生成するもの
指数形式; c = 任意の整数	整数 m > 1	Ac の多項式形式、ここで A は GF(pm) の "既定" の原始多項式の根です。
例: tp = gftuple(6,2,3); % c = 6 here
指数形式; c = 任意の整数	原始多項式の係数のベクトル	Ac の多項式形式、ここで A は "与えられた" 原始多項式の多項式形式の根です。
例: polynomial = gfprimdf(2,3); tp = gftuple(6,polynomial,3); % c = 6 here
任意の次数の多項式形式	整数 m > 1	簡略化するために GF(pm) に "既定" の原始多項式を使用する、次数 < m の多項式形式
例: tp = gftuple([0 0 0 0 0 0 1],2,3);
任意の次数の多項式形式	原始多項式の係数のベクトル	簡略化するために GF(pm) に "与えられた" 原始多項式を使用する、次数 < m の多項式形式
例: polynomial = gfprimdf(2,3); tp = gftuple([0 0 0 0 0 0 1],polynomial,3);

上記の表の 4 つの例は、すべて同じベクトル tp = [2, 1] を生成しますが、gftuple に対する異なる入力は、表の行に対応します。各例は、A⁶ = 2+A であるという事実を示します。ここで、A は GF(3²) に対する (既定の) 原始多項式 2 + x+ x² の根です。

例

この例は、GF(3⁴) の 2 つの多項式形式の元を乗算するために、gfconv と gftuple を組み合わせる方法を示します。最初に、gfconv は、原始元を変数のように扱って、2 つの多項式を乗算します。これは高次の多項式を生成し、原始元が満たす多項式を使用して関数 gftuple により簡略化されます。最終結果は、最も簡単な多項式の積の形式です。

p = 3; m = 4;
a = [1 2 0 1]; b = [2 2 1 2];
notsimple = gfconv(a,b,p) % a times b, using high powers of alpha
simple = gftuple(notsimple,m,p) %Highest exponent of alpha is m-1

出力は以下のようになります。

notsimple =

     2     0     2     0     0     1     2


simple =

     2     1     0     1

例:ガロア体の元のリストの生成.  この例は、ガロア体のすべての元をリストする行列を生成する作業に、変換機能を適用します。体のすべての元をリストする行列は、gfadd や gfmul のような関数の入力引数です。下記の変数 field1 と field2 は、そのような関数が期待する形式です。

p = 5; % Or any prime number
m = 4; % Or any positive integer
field1 = gftuple([-1:p^m-2]',m,p);

prim_poly = gfprimdf(m,p); % Or any primitive polynomial
% for GF(p^m)
field2 = gftuple([-1:p^m-2]',prim_poly,p);

最も簡単な指数形式への変換.  同じ関数 gftuple は、指数表現または多項式表現を与えられると、GF(p^m) の元の最も簡単な指数表現も生成します。この出力を得るには、以下の構文を使います。

[polyformat, expformat] = gftuple(...)

入力形式と出力 polyformat は、初めの 2 つの入力の形式に依存する gftuple の動作 の表のとおりです。さらに、変数 expformat は、polyformat で表現される元の最も簡単な指数形式を含みます。これは、指数が -Inf または 0 から p^m-2 の間の数値であるという点で、"最も簡単" なものです。

例

前節で説明した元 2 + A の指数形式を復元するには、下記のコマンドを使います。この場合、polyformat は冗長な情報を含み、expformat は必要な結果を含みます。

[polyformat, expformat] = gftuple([2 1],2,3)

polyformat =

     2     1

expformat =

     6

この出力は、最初は表 GF(9) の元の情報と矛盾するように見えますが、実際はそうではありません。表は、異なる原始元を使っています。その原始元に 2 を加えると、下記の多項式形式および指数形式をもちます。

prim_poly = [2 2 1];
[polyformat2, expformat2] = gftuple([2 1],prim_poly,3)

下記の出力は、表の一番下の行の情報を反映しています。

polyformat2 =

     2     1


expformat2 =

     7

ガロア体の演算

• この節の概要

• 素体の演算

• 拡大体の演算

この節の概要.  関数 gfadd, gfsub、gfmul、gfdiv を使用して、それぞれガロア体の元の加算、減算、乗算、除算を行うことができます。これらの関数のそれぞれは、素体に対するモードと拡大体に対するモードをもちます。

素体の演算.  GF(p) の演算は、演算 modulo p と同じです。関数 gfadd, gfmul, gfsub, gfdiv は、GF(p) の元を 0 から p-1 の間の整数として表す 2 つの引数を受け取ります。3 番目の引数は p を指定します。

例:GF(5) の加算表

下記のコードは、GF(5) に対する加算表を構築します。a と b が 0 ～ 4 の場合、元 gfp_add(a+1,b+1) は GF(5) の和 a+b を表します。たとえば、2+4 は 1 modulo 5 なので、gfp_add(3,5) = 1 です。

p = 5;
row = 0:p-1;
table = ones(p,1)*row;
gfp_add = gfadd(table,table',p)

この例の出力は、次のようになります。

gfp_add =

     0     1     2     3     4
     1     2     3     4     0
     2     3     4     0     1
     3     4     0     1     2
     4     0     1     2     3

その他の p の値は、異なる素体 GF(p) の表を作成します。gfadd を gfmul、gfsub、または gfdiv で置き換えると、GF(p) の対応する算術演算用の表が生成されます。

拡大体の演算.  同じ算術関数は、m > 1 のとき GF(p^m) の元を加算できますが、引数の形式は、上記の場合よりも複雑です。一般に、拡大体の算術演算は、素体の算術演算よりも複雑です。算術演算の機能に関しては、ガロア体の参考文献 の文献を参照してください。

拡大体での実行時に、関数 gfadd, gfmul, gfsub, gfdiv は最初の 2 つの引数を指数形式で使用して、GF(p^m) の元を表します。必須である 3 番目の引数は、ガロア体のすべての元のリスト のように GF(p^m) のすべての元をリストします。結果は、指数形式です。

例:GF(9) の加算表

下記のコードは、GF(9) に対する既定の原始多項式の根に対する指数形式を使って、GF(3²) に対する加算表を構築します。a と b が -1 ～ 7 の間である場合、元 gfpm_add(a+2,b+2) は、GF(9) の A^a と A^b の和を表します。たとえば、gfpm_add(4,6) = 5 ですが、これは次の理由によります。

A² + A⁴ = A⁵

行列 field の 4 行目と 6 行目を使用して、以下を確認することができます。

A² + A⁴ = (1 + 2A) + (2 + 0A) = 3 + 2A = 0 + 2A = A⁵ modulo 3.

p = 3; m = 2; % Work in GF(3^2).
field = gftuple([-1:p^m-2]',m,p); % Construct list of elements.
row = -1:p^m-2;
table = ones(p^m,1)*row;
gfpm_add = gfadd(table,table',field)

出力は以下のようになります。

gfpm_add =

  -Inf     0     1     2     3     4     5     6     7
     0     4     7     3     5  -Inf     2     1     6
     1     7     5     0     4     6  -Inf     3     2
     2     3     0     6     1     5     7  -Inf     4
     3     5     4     1     7     2     6     0  -Inf
     4  -Inf     6     5     2     0     3     7     1
     5     2  -Inf     7     6     3     1     4     0
     6     1     3  -Inf     0     7     4     2     5
     7     6     2     4  -Inf     1     0     5     3

メモ

他の原始多項式を使った場合は、表は異なります。これは、表の行と列の順序が GF(9) の元の自然な順序ではなく、特定の原始多項式の選択に基づくためです。

その他の p と m の値は、異なる拡大体 GF(p^m) の表を作成します。gfadd を gfmul、gfsub、または gfdiv で置き換えると、GF(p^m) の対応する算術演算用の表が生成されます。

素体上の多項式

• この節の概要

• 多項式の表示の変更

• 多項式の演算

• 多項式の特性

• 多項式の根

この節の概要.  GF(p) 上の多項式は、係数が GF(p) の元である多項式です。Communications Toolbox ソフトウェアには、以下を行うための関数が用意されています。

• 多項式の表示方法の変更

• 多項式演算を実行する

• 原始あるいは既約として多項式を特徴付ける

• ガロア体の多項式の根を求める

  メモ

  本ツールボックスのガロア体関数は、係数を変数の "昇べき" 順に並べたベクトルとして奇数 p に対する GF(p) 上の多項式を表します。これは、他の関数 MATLAB が使用する順序とは逆です。

多項式の表示の変更.  係数を含む行ベクトルに対応する多項式を従来通りに書式化して表示するには、gfpretty を使用します。多項式の次数よりも "高い" 指数をもつすべてのゼロ係数項を除去して多項式を短縮するには、gftrunc を使用します。次に例を示します。

polynom = gftrunc([1 20 394 10 0 0 29 3 0 0])
gfpretty(polynom)

出力は以下のようになります。

polynom =

     1    20   394    10     0     0    29     3


                                   2       3       6      7
                   1 + 20 X + 394 X  + 10 X  + 29 X  + 3 X

メモ

固定幅フォントを利用しない場合は、表示内のスペースは正確でない場合があります。

多項式の演算.  関数 gfadd と gfsub は、それぞれ GF(p) 上の多項式の加算と減算を行います。関数 gfconv は、GF(p) 上の多項式を乗算します。関数 gfdeconv は、GF(p) 内の多項式を除算し、商の多項式と剰余の多項式を生成します。たとえば、下記のコマンドは、体 GF(3) 上で 2 + x + x² と 1+x を乗算すると、2 + 2x² + x³ になることを示します。

a = gfconv([2 1 1],[1 1],3)
[quot, remd] = gfdeconv(a,[2 1 1],3)

出力は以下のようになります。

a =

     2     0     2     1


quot =

     1     1

remd =

     0

前述した関数 gfadd と gfsub は、それぞれ多項式の加算と減算を行います。多項式を表すために係数のベクトルを使用するため、MATLAB は、2 つの多項式の加算と、2 つの行ベクトルの要素単位の加算を区別しません。

多項式の特性.  GF(p) 上の多項式について、関数 gfprimck は、既約多項式および/または原始多項式かどうかの判定を行います。定義では、原始多項式である場合は既約です。しかし、その逆は必ずしも真ではありません。関数 gfprimdf と gfprimfd は原始多項式を返します。

GF(p^m) の元を与えると、関数 gfminpol は、GF(p) 上の最小多項式を計算します。

例

たとえば、下記のコードは、すべての最小多項式の非既約性を反映します。しかし、非原始元の最小多項式は、原始多項式ではありません。

p = 3; m = 4;
% Use default primitive polynomial here.

prim_poly = gfminpol(1,m,p);
ckprim = gfprimck(prim_poly,p);
% ckprim = 1, since prim_poly represents a primitive polynomial.

notprimpoly = gfminpol(5,m,p);
cknotprim = gfprimck(notprimpoly,p);
% cknotprim = 0 (irreducible but not primitive)
% since alpha^5 is not a primitive element when p = 3.

ckreducible = gfprimck([0 1 1],p);
% ckreducible = -1 since the polynomial is reducible.

多項式の根.  GF(p)上の多項式について、関数 gfroots は、適切な拡大体 GF(p^m) の多項式の根を求めます。拡大体 GF(p^m) の次数 m を MATLAB に通知するためには、下記の表に示すように 2 つの方法があります。

gfroots の 2 番目の引数の形式

2 番目の引数	表現
正の整数	多項式 GF(pm) の m。MATLAB は既定の原始多項式を計算に使用します。
行ベクトル	GF(pm) の原始多項式。m は、この原始多項式の次数です。

例:GF(9) の多項式の根

下記のコードは、GF(9) 内の多項式 1 + x² + x³ の根を求め、それらが実際に根であることを確認します。GF(9) の元の指数形式が最初から最後まで利用されます。

p = 3; m = 2;
field = gftuple([-1:p^m-2]',m,p); % List of all elements of GF(9)
% Use default primitive polynomial here.
polynomial = [1 0 1 1]; % 1 + x^2 + x^3
rts =gfroots(polynomial,m,p) % Find roots in exponential format
% Check that each one is actually a root.
for ii = 1:3
   root = rts(ii);
   rootsquared = gfmul(root,root,field);
   rootcubed = gfmul(root,rootsquared,field);
   answer(ii)= gfadd(gfadd(0,rootsquared,field),rootcubed,field);
   % Recall that 1 is really alpha to the zero power.
   % If answer = -Inf, then the variable root represents
   % a root of the polynomial.
end
answer

出力は、A⁰ (1)、A⁵、A⁷ が根であることを示します。

roots =

     0
     5
     7


answer =

  -Inf  -Inf  -Inf

gfroots が根の多項式形式や体のすべての元のリストを表示する方法については、gfroots のリファレンス ページを参照してください。

その他のガロア体関数

Communications Toolbox ソフトウェアのその他のガロア体関数に関する情報は、オンライン リファレンス ページを参照してください。

• gfcosets、円周等分剰余類を生成

• gffilter、GF(p) 多項式を使用してデータをフィルター処理

• gfprimfd、原始多項式を求める

• gfrank、GF(p)上の行列のランクを計算

• gfrepcov、バイナリ多項式表現を別の表現に変換

ガロア体の参考文献

[1] Blahut, Richard E., Theory and Practice of Error Control Codes, Reading, Mass., Addison-Wesley, 1983.

[2] Lang, Serge, Algebra, Third Edition, Reading, Mass., Addison-Wesley, 1993.

[3] Lin, Shu, and Daniel J. Costello, Jr., Error Control Coding: Fundamentals and Applications, Englewood Cliffs, N.J., Prentice-Hall, 1983.

[4] van Lint, J. H., Introduction to Coding Theory, New York, Springer-Verlag, 1982.

×

例を開く

この例の変更されたバージョンがあります。編集された方の例を開きますか?

いいえ、変更されたバージョンを上書きします。 はい