符号理論 ½ 始めに ½º½ 情報伝送モデル 情報理論における情報伝送のモデルを図に示す。 情報記号系列 → 符号語系列 → 伝送路 → 受信記号系列 → 復号記号系列 → 情報記号系列 ↑ 誤り記号系列 文章，静止画，動画，音声等の伝達したい情報のバイナリ化した情報記号系列に冗長符号を追加して符号語 系列に変換する。符号語が伝達される際にノイズやハードウェアのエラーにより誤り記号系列が付け加わっ たものが先方へ伝わる。受信された記号列は受信記号系列といわれ，これより誤り記号系列を推定して修 正された復号記号系列を得て伝達したい情報を取り出す。 ½º¾ アナログ通信での工夫 放送のように ÓÒ ßÛ Ý の通信と、電話のように ØÛÓßÛ Ý の通信では誤りへの対策は異なるであろうが、 聞き取りにくい電話で会話するには次のような対策が考えられる。 ¯ ¯ ¯ ¯ ¯ ¯ 大声で話す ゆっくり話す 繰り返す 復唱する ´Ø Ð µ 言い換えて話す 符号化して伝える ´新聞の し 、濁点、ヨットの よ 、上野の う 、 µ ½º¿ 符号理論の歴史 アナログ通信の時の考えから、ゆっくり伝送すれば伝送誤りは ¼ に近づくことが分かるが、それでは大 º ºË ÒÒÓÒ が ½ 年に Å Ø Ñ Ø Ð Ø ÓÖÝ Ó ÓÑÑÙÒ Ø ÓÒ º で今日 通信路符号化定理と呼ばれる次の定理を発表した。この定理はシャノ ンの発表した情報理論の基本定理の内の一つである。 量の情報を伝えるにはコストが大きくなる。この問題に対し 定理 ½ ´シャノンµ 伝送速度がこの通信容量を越えない限り、伝送速度を ¼ に近づけることなく一定にし たままで ´ 冗長度を一定にしたままで µ、符号化と復号化を工夫すれば誤り率はいくらでも小さくできる。 ここで「通信容量」とは通信路の物理定数で，通信電力や通信周波数などで決まる。また， 「冗長度」とは これから先に説明する情報源の信号以外に付け加えられる誤り検出・修正符号を意味する。 ½ この定理に触発されて色々な符号化の理論 ´符号理論 ´ Ó Ò Ø ÓÖݵµ が研究されることとなった。基本 になる数学の理論は代数学であるが、妥当性の検証に統計学も利用される。符号理論の研究の成果として 今日の光ディスクや深宇宙通信が成立しているのである。 ¾ 定義、概念、実例 ¾º½ 符号の概念 符号の種類 ディジタル通信では、放送や電話のようなアナログ通信と違って、情報源から送り出された信 号は直接変調されて通信路へ送り出されるわけではない。情報源の信号を連続的に符号化して送出する場 合と、ある程度まとまったものを符号化して送出する場合とに分けられる。連続的に符号化される符号系を 合流符号 ´ ÓÒÚÓÐÙØ ÓÒ Ó µ といい、ある程度まとまったものを符号化する符号系をブロック符号 ´ ÐÓ Ó µ という。 合流符号では木構造グラフが符号化の表現に使用されるために、木符号とも呼ばれる。この方式の符号を 復号する原理では¸ 復号する信号列がそれまで受信した信号と係わり合っているので，合流の名前がある。 一方のブロック符号は次のような特徴がある。 ¯ 情報記号系列は一定の長さ毎にまとめられ，ブロック化される。これを情報記号ベクトルともいう。 ¯ 情報記号ブロックに冗長記号が追加されて一定の長さの記号系列に変換される。変換された記号列を 符号語ベクトルという。 ¯ 復号は原則としてブロック単位で行われる。即ち、木符号と異なりブロック符号では、復号は互いに 独立に行われる。 どちらの方式も何らかのアルゴリズムにより復号するのであるが、この講義ではブロック符号について説 明する。 ¿ ブロック符号 ¿º½ É ハミング距離 を 定義 ½ Õ 個の記号の集合とする。ÉÒ を Ò¿Ü Ý をÜ É ´Ü½ ܾ Ü É の元を要素とする Òµ Ý ´Ý½ ݾ Ò Ò µ とするとき Ò Æ ´Ü Ý µ Ý À ´Ü Ý µ ½ ただし ´ Æ Ü Ý À ´Ü ݵ を Ü Ý の ハミング距離 ´À ÑÑ Ò µ ½ Ü Ý ¼ Ü Ý ×Ø Ò µ という。 Û 次元の横ベクトルとする。 ´Üµ À ´Ü ¼µ ¾ ص という。ただし、¼ はゼロベクトルである。 ハミング距離は Ü Ý の成分の異なるものの個数を表す。ウェイトは ¼ でない成分の個数を表す。また、 ´Üµ Ý ¾ ÉÒ À ´Ü ݵ を中心 Ü、半径 の球 ´×Ô Ö µ と呼ぶ。球という言い方は次の定理か らも妥当である。 を Ü の重み ´Û 定理 ¾ ハミング距離は距離の公理をみたす。 略証 反射律と対称律は明らかだから、三角不等式だけ証明すればよい。また、三角不等式は Æ ´Ü Ý µに 対していえればよい。 ¾ É を任意に取る。Æ ´Ü Þ µ ¼ ならば明らか。Æ ´Ü Þ µ ½ ならば Ü Þ 、このとき Ý と Ü Þ との関係 Ý または Ü Ý Þ Ý または Ü Ý Þ であるから、どの場合も Æ ´Ü Ý µ· Æ ´Ý Þ µ ½ Æ ´Ü Þ µ となる。 Ü Ý Þ はÜ Ý Þ ¿º¾ ブロック符号 定義 ¾ Ò の部分集合 É をブロック符号 ´ ÐÓ Ó µ、その元を符号語 ´ Ó ÛÓÖ µ、Ò を 符号長 ´ Ó Ð Ò Ø µ という。また、 ´ µ を最小距離 ´Ñ Ò ÑÙÑ ×Ø Ò µ、 Û を最小重み ´Ñ Ò ÑÙÑ Û Øµ、Õ É ´ µ ÑÒ を符号化率 ´ Ò ÓÖÑ Ø ÓÒ Ö Ø ¸ Ö Ø Ó ´ µ Ó Ò µ、 Ñ Ü ÑÒ Ù×µ という。被覆半径 の最大値であるから，被覆半径 は球の集合 定義 ¿ ´Üµ Ü ¾ ÐÓ Õ ´ µ を被覆半径 ´ ÓÚ Ö Ò Ö 完全符号、 Û として Ö ¿º¿ À ´Ü Ý µ Ü Ý ¾ ÑÒ À ´Ü µ は各 ¾ Ü ¾ ÉÒ Ü ¾ ÉÒ から ´ µ の元までの最小距離の Ü ¾ ÉÒ 全体 Ò が É 全体を覆うための最小距離である。 ¾ 、 受信語の × 個以下の間違いを検出できる符号系を ×ß誤り検出符号 ´×ß ÖÖÓÖ 以下の間違いを正しい符号に訂正できる符号系を Øß誤り訂正符号 ´Øß ÖÖÓÖ 最小距離が ´ µ のブロック符号は ´ µ ¾× のとき ×ß誤り検出符号、 ´ µ ÖÖ Ø Ò Ø Ø Ò Ó µ、Ø 個 Ó µ という。 ¾Ø · ½ とするとき、Øß誤り 訂正符号である。 定義 最小距離が ¾Ø · ½ の符号 É Ò が完全符号 ´Ô Ö Ø Ó µ とは、全ての Ü ¾ ÉÒ が距離が Ø 以 下の範囲に唯一つの符号語がある場合をいう。 完全符号は最小距離が ¾Ø · ½ で、被覆半径が Ø であることと同値であるから、Ø 個までの誤りを含む受信 語を正確に誤り訂正できる。即ち、Øß ÖÓÖ ÓÖÖ Ø Ò Ó ¿ である。 定義 受話語から最小距離にある符号語を見つけ出す方法を最小距離復号法：Å 法 ´Ñ Ò ÑÙÑ ×Ø Ò Ó Ò µ という。 例½ 反復符号 ´Ö Ô Ø Ø ÓÒ Ó µ É ¼ ½ Ò を奇数として、情報記号系列が ¼ または ½、それぞれを Ò 回繰り返した信号列を符合とす るブロック符合を反復符号という。このブロック符号の最小距離は Ò、符号化比率は ½ Ò である。 符号長を とすると Ü ´¼¼¼¼¼µ Ý ´½½½½½µ で、最小距離は である。したがって、 ¾ ·½ より ¾ 個までの誤りは全て正しく訂正できることになるが、この場合、正しい送信符号の決定に Å 法 の他に，受信語の ¼ ½ の個数を比べて，多い方を復号語とする多数決法が考えられる。これは Å 法と 同じ結果を得るが復号アルゴリズムはより簡単である。 Ü Ý と距離が ½ にある É の元は各 個、距離が ¾ なるものは各 ½¼ であるから、合計 ¿¼、し ¾ たがって、被覆半径は ¾ で反復符号は完全符号である。´Ò が一般の場合も同様に証明できるµ 例¾ パリティ検査符号 ´Ô Ö ØÝ Ó µµ É ¼ ½ 、É を情報記号系列全体とする。情報記号ベクトルの最後に ¼ または ½ を付け加えて，ベ クトル ´¾ É ·½ µ の ½ の個数が偶数になるようにしたものを符号語としたブロック符号を考える。最後に付 け加えられる成分を ´パリティµ 検査部ということにする。 情報記号系列は最低 ½ 箇所は、成分が異なる。さらに、½ 箇所成分が異なると ´パリティµ 検査部の値も 異なってくるので、この符号の最小距離は ¾、従って ½ß ，符号化率は ´ · ½µ である。 この符号は受信語の ½ の個数が奇数個であったら受信語に誤りがあることが分かるが訂正はできない。 この符号は計算機本体とキーボード間や Ä Æ 内での通信に広く使用されている。間違いが検出されたら 再送信を依頼すれば誤りが少なくなる。 誤り確率を考慮した場合 伝送の際にビット落ちを起こす場所が確定している場合はエラーの検出は容易 である。現実にはノイズの混入はランダムに起きるので、現象解析には統計的な考慮も必要である。 É ¼ ½ のとき ¾ 元符号といい、¼ ½ の ¾ つの信号が伝送の際に同じ確率 でそれぞれ ½ ¼ と読み誤 られる通信路を ¾ 元対称通信路、同じ確率で信号が消えてしまう通信路を ¾ 元対称消失通信路という。 受信語から送信された正しい符号語を推定するのに、統計的推定を利用する方法があるが、 Ò½ Ò¾ に 対し Ò½ 個のエラーのあるエラーパターンより、Ò¾ 個のエラーのあるエラーパターンの方が真実に近い と いう考えで元のパターンを推定する方法を最尤復号法：ÅÄ ´Ñ Ü ÑÙÑ Ð ÓÓ Ó Ò µ という。 誤り確率 の ¾ 元対称通信路の場合は、受信語 Ý、符号語 Ü に対し À ´Ü Ý µ とすると Ü を Ý と受信される確率は È ´Ü ݵ ´½ µÒ であるから、 が最小のものが最も送信語に近いと推定することにすると、これは Å 得る。 法と同じ結果を 復号アルゴリズムの複雑さ アルゴリズムの良さを判定する指標として、アルゴリズムの時間的複雑さとい う考えがある。これは、長さが Ò の入力に対して問題解決までに主要なループを何回通るかを表したもの である。解析学で ¾ つの関数 ´Üµ ´Üµ を考え、Ð ÑÜ ½ ´Üµ ´Üµ が ¼ でない定数のとき は同位 であるという。あるアルゴリズムの時間的複雑さを ´Òµ としたとき、 ´Òµ が Ò ÐÓ ´Üµ と ´Üµ の多項式と 同位ならば多項式時間のアルゴリズムであるといい、Ò の指数関数や Ò と同位ならば指数関数時間のアル ゴリズムであるという。指数関数時間のアルゴリズムは計算機がどんなに早くなっても、入力データが大き くなると問題解決に非現実的な時間を要する。即ち、計算機で解けない問題になってしまうのである。 復号のアルゴリズムに関しては Å 法でも、ÅÄ 法でも、受信語に対して、ブロック符号 の全て の要素と比較しなければならないので、指数関数的時間がかかる。 良い符号 Ò 以上のことを考慮して良い符号とは最低次のような条件を満たさなければならないことが分か るであろう。 ¯ 信頼性：復号誤り確率が小さいこと ¯ 効率： 符号化比率が大きいこと ¯ 復号の複雑さ： 復号のアルゴリズムの時間的複雑さが小さいこと 代数からの準備 ´½µ º½ 有限体 符号を何らかの数学的構造を持って定義することを考える。以下において次の代数の主要な定理を利用 する。 ¯ 符号の要素 É は有限体とする ´殆どの場合は と表されガロア体と呼ばれる。 ¯ 有限体 É の元の個数を 数という。 £ ¯ 有限体 É の乗法群 É ¼ ½ « «¾ «¿ É É É Õ ¾ « Õ É ¼ ½ の ¾ 元体であるµ。É は とすると、Õ はある素数 ¼ は É Ô のべき乗 Õ ´Õ µ または Õ Ö である。Ô を体 Ô É の標 のある要素 «´原始元というµ の巡回群で表される。即ち、 が素数のとき、有限体 Ô は整数の有限集合 É ¼ ½ ¾ Ô ½ に Ô を法とした四則計算を考えれ ばよい。この場合は ¼ ½ 以外の任意の É の元が原始元である。また、Õ ÔÖ ´Ô ÔÖ Ñ µ のとき有限体 Õ Ô は Ô を係数とする多項式環 Ô Ü の Ö 次の既約多項式 Դܵ による剰余多項式全体の集合 Ô Ô´Üµ を法とした四則計算を考えればよい。この場合は、一次式 Ü が一つの原始元である。 º¾ Ü ´Ô´Üµµ に 有限群とコセット分解 有限群 である。この同値類を に行う。 を考える。 ½ ¾ À´ ½ ¾ ´µ ¾ µ とすると、この関係は同値関係 の À による ´左µ コセット分解という。コセット分解を具体的行うには次のよう とその部分群 À ´½µ ½ À ¾ Ñ を ¿ À の要素とする。ここで は群の単位元で、 ¾ 以降は任意に並べ てよい。 ´¾µ ¾ ¾ を ¾ ¾ À に任意に取り ¾ À ¾ ½ ¾ ¾ ¾ ¾ ¿ ¾ Ñ を考える。 ´¿µ ¿ ¾ を ¿ ¾ À À に任意に取り、 À ¾ ¿ ¿ ½ ¿ ¿ ¾ ¿ ¿ ¿ Ñ を考える。 ´ µ 同じ要領で繰り返すと表に現れる元は全て異なり、 の元は有限だから、有限回の操作で終了する。 ´ µ 同値類の個数を Ð とすると À ¢ Ð の関係にある。 ¡¡¡ À と Ð À と表すことができる。コセット類を表すのに 記す。この分解で ¾ ¿ Ð をコセットリーダという。数学では同値類の代表元とよんでいる。コ セットリーダーの選び方は一意ではない。同じ同値類の任意の元がコセットリーダになる。 この操作の結果を ¾À À ¿ 線形符号 º½ 諸定義 定義 É の元を要素とする長さが Ò の符号 形部分空間を作るものをいう。 の次元が ´Ò µ 符号であると呼ばれる。 線形部分空間であるとは Ü Ý¾ µ であるとは、 が ÉÒ の線 µ 符号、また、最小距離が を付け加えて が Õ 元線形符号 ´但し のとき ならば Ü Ý ¾ は ´Ò Õ É であることを意味する。ここで、Ü Ý は成分ごと の引き算を行う。ただし，引き算は有限体の規則で行われる。線形部分空間のもう一つの計算であるスカ ラー倍は表面的には使われない。 線形符号は符号のクラスの中で基本的なものであり、殆どの符号が線形符号を基にして構成されている。 定理 略証 ¿ 線形符号においては最小距離は最小重みと同じである。 線形符号 において、任意の符号語 À ´Ü ݵ 生成行列 を ܽ ܾ が Ü Ü Ý をとると線形性より Ü Ý ¾ À ´Ü Ý ¼µ Û であるから ´Ü ݵ 個の一次独立なベクトル ´基底µ がある。その一組 次元の線形空間であるから、 には ´注：横ベクトルµ とすると， ¾ が成立する。そこで ´µ ´ 行 Ò 列の行列 ½ ¾ を µ´ ½ ܽ ¼½ · ¾ ܾ ·¡¡¡· Ü µ ܽ ܾ ºº º Ü ¾ É が成り立つ。この性質から を の生成行列という。基底の選び方は一意的 でないので、生成行列も一意的でないが、 ´Á È µ 形の生成行列を標準形の生成行列という。ここで Á は 次の単位行列で È は 行 Ò 列の行列である。線形符号の特徴は行列 È により表される。 とおくと ´Û Ôµ ´Ô は Ò 次のベクトルµ であるから、符号語の先頭から 個の記号を情報記号列 ´ Ò ÓÖÑ Ø ÓÒ ×ÝÑ ÓÐ×µ、 ×ÝÑ ÓÐ×µ という。情報記号列の部分は任意に定められる 残りの記号をパリティ検査記号列 ´Ô Ö ØÝ が、パリティ検査記号列は情報記号列に依存している。 生成行列が標準形のとき、情報記号ベクトル 例¿ Û ¾ É に対して生成される符号語ベクトルは Û 反復符号、パリティ検査符号の生成行列はそれぞれ ´½½ である。ここで ´½½½½½½½µ で ½Ì はそれを転置した縦ベクトルを表す。 ½ ¾ つの線形符号 定義 ´Á ½Ì µ ½µ ½ ¾ はその生成行列が行基本変形と列置換で一致するときに等価 ´ ÕÙ Ú Ð Òص と いう。 ¢ Ò 行列は階数が ならば、行基本変形と列の置換だけで ´Á È µ の形に変 形できるできるから、等価であることは生成行列の標準形が行列 È の列の置換で一致することと同じであ る。 ½ ¾ が等価ならば、そのベクトルはある一つの置換で成分を入れ替えると一致することが分かる。こ のことより、等価な符号ならば誤り訂正能力は同じである。 行列の一般論から 定義 一般に符号 が 個の位置で 組織的 ´×Ý×Ø Ñ Ø µ とは、 度一つの情報記号列に対応しているものをいう。この場合その Õ でその 個の位置の値が丁 個の場所にある記号は情報記号と呼ばれ る。また、この場合のように情報記号と冗長記号が区別できるような符号は分離的 ´× Ô Ö Ð µ であると呼 ばれる。 標準形の生成行列から生成される線形符号は組織的で、分離的である。 定義 が ´Ò µ 符号のとき、符号 Ý¾É を の双対符号 ´ Ù Ð Ó Ü¾ ´ Ü Ý ¼µ ただし ÜÝ は内積 µ という。 µ 符号である。ここ で係数体は有限体であるから、実数上のベクトル空間と異なり ¼ とは限らないないことに注意 すると、 のとき、 は自己双対 ´× Ð ß Ù Ðµ 符号であると呼ばれる。 ´Á È µ を の標準形の生成行列ならば、Ò 行 Ò 列の行列 À ´ È Ì ÁÒ µ は の生成行列 Ì である。何故ならば、 の生成行列を À とすると Ü Ý ÜÝ であって、任意の Ü Ý はそれぞれ Ì Ì Ì より、この値が任意の Ü Ý À と表されるから ÜÝ ´ Àµ À に対して Ì 成立するためには À Ç でなければならない。 ´Á È µ のとき À Ç ´µ À ´ È Ì ÁÒ µº さらに、任意の Ü ¾ は Ü と表されることから 直交補空間は線形空間であるから双対符号も線形符号である。即ち、 Ü ¾ ´µ ÜÀ Ì Ç は ´Ò Ò 定義 ½¼ ´½µ Ý ¾ 行列 に対し、任意の Ü ¾ À を をパリティ検査 ´方程式µ、 の生成 のパリティ検査行列という。 ´¾µ 線形符号 のパリティ検査行列が ´×ÝÒ ÖÓÑ µ という。 º¾ ÜÝ に対し成立する方程式 À ܾ のとき、任意の É Ò に対して ÜÀ Ì を Ü の シンドロム 線形符号の復号 シンドロムの構成 ベクトル空間 ÉÒ と部分空間 ロムの関係を考える。 ÜÀ Ì を加法群と部分群の関係と見たコセット分解とシンド ÝÀ Ì ´µ ´Ü ݵÀ Ì ¼ ´µ Ü ¾ Ý · であるからコセット類とシンドロムは一対一に対応する。 ´½µ コセット分解の手順を繰り返しておくと ¼ ¼，次に ½ ´½¼ ¼µ，次は ¾ ¾ ´ ½ · µ， Ò ´ ½· µ ´ ¾· µ と続ける。 É を ´Ò µ 符号とすると、必要なシンドロムは ¿ ¾ Ò Õ 個 ´ただし ´Õ É µ である。 ´¾µ 符号の復号の場合はコセットリーダはウェイトの小さいものから選ぶ。始めはウェイト ½ のものから ´½¼ ¼µ ¾ ´¼½¼ ¼µ ¼½µ の順に選ぶのが通常の方法である。 の最小ウェ ½ Ò ´¼ イトが ½ の場合はコセットリーダーに自然な基底を選んでいるうちにコセットリーダの選出が終わっ てしまうが，¾ 以上の場合は少なくとも自然な基底はすべて選出される。 ´¿µ 続いて Ò·½ ´½½¼ ¼µ Ò·¾ ´¼½½¼ ¼µ などとウェイトが ¾ のものからコセットリーダを選ぶ。 ´ µ の最小ウェイトが大きいときは，更に，ウェイトが ¿ のベクトルというように続き， Õ Ò 個のコ セットリーダが得られるまで実行する。 ´ µ 得られた一組のコセットリーダ ½ ¾ Ö を用いて一組のシンドロムを次により得る。 × À Ì ½ Ö ´Ö Õ Ò µ シンドロムによる復号 線形符号 のパリティ検査行列を À とする。パリティ検査行列やシンドロムの 定義 ½¼ から、符号語 Ü ¾ に誤りベクトル が付け加わって Û Ü · を受信したとすると ÛÀ Ì Ì であるから受話語のシンドロームを求めて、同じシンドロムのコセットリーダを誤りベ ´Ü · µÀ Ì À クトルであると推定することは妥当な方法である。コセットリーダの選び方を上で説明したようにウェイト の小さいものから選ぶようにするとシンドロムを用いた復号は次のように行われる。 ´½µ 受話語 Û のシンドロム × ÛÀ Ì を求める。 ´¾µ 上で求めたシンドロムの一覧から × と同じものを求める。それを × × とする。 ´¿µ × に対応するコセットリーダ を求め、Ü Û を復号符号語と推定する。 コセットリーダはウェイトの小さいものから選んでいるので，この復号法は Å 法と等価である。コセッ トリーダのウェイトが大きい所では、同じシンドロムに対して同じウェイトのコセットリーダの候補は複数 ある可能性があるので、この場合は復号語候補が複数あることを意味するが、復号は固定したコセットリー ダを用いて行う。 以上に説明した方法でコセットリーダを選ぶと ½ ´½¼ ¼µ ¾ ´¼½¼ ¼µ ¼½µ に対応 Ò ´¼ Ì するシンドローム ×½ ×Ò ×Ò はパリティ検査行列 À を転置したもの À の行に現れる。即ち、 ¼½ ×½ ×¾ ºº º À Ì ×Ò ºº º 復号誤り率 ¾ 元対称通信路において ¾ 元 ´Ò される確率 È ´ µ は µ 線形符号 定理 È でる。ここで、和は ¼ から 数で、 は ¼ ½ または ½ ´ µ Û ¼ Û のシンドロムによる復号を考えると、正しく復号 Û ´½ µÒ Û までのウェイトに関するもので、 Û はウェイトが Û のコセットリーダの個 ¼ の読み誤り確率である。但し、符号語の全文書中の使用割合は同じとする。 ½ Ö を一組のコセットリーダとするとシンドロムによる復号法から、一つの符号語を 正しく伝達できる受話語は一つの符号語 Ü に対して Ü · ½ Ö に限られるから、その語に読 み誤られる確率を求めればよい。 のウェイトが Û のとき Ü を Ü · に読み誤る確率は Û ´½ µÒ Û である。したがって、ウェイトが Û のコセットリーダが Û 個あれば、これらに誤って伝送される確率は Û Ò Û である。これより符号語 Ü の通信文中に占める割合を È ´Ü µ とすると符号 の全文の正 Û ´½ µ しく復号される確率は 証明 ¾ È ´ µ È ½ 仮定から È ´Ü µ ´Ü µ Û ¼ Û Û ´½ µÒ Û ½ ¾ であるから定理の式を得る。実際の和は の最小ウェイトを越えたところにはシン ドロムはない。 ハミング符号 重要な例であるハミング符号の説明をする。 定義 ½½ の有限体 Õ 上の ´Ò µ 線形符号 を考える。 は 行 Ò 列の行列であるが、 の任意の ¾ つの縦ベクトルが一次独立 ´即ち、一方が他方のスカラー倍でないµ のとき、 を射影符号 ´ÔÖÓ ØÚ 一般に、 には 生成行列が Ó µ という。 のパリティ検査行列になり、任意の Ü とウェイト ½ のエラーベクトル ´具体的 ¼ ¼ ¼µµ に対し、シンドロム ´Ü · µ Ì は の縦ベクトルのスカラー倍 ´具体例で は双対符号 ´¼ は 列の縦ベクトルのスカラー倍µ になる。 に上記の制限が付くとシンドロムから のどの列に対応し ているか直読できることから、エラーベクトルが直ちに分かる。即ち、 正できる符号である。 と は少なくとも ½ 個のエラーは訂 を入れ替えて，この性質を一杯に使用したものが次のハミング符号である。 Õ 上の 次元ベクトル空間 É のベクトルの集合で任意の ¾ 本が一次独立 である最大のものの元の個数を調べてみる。始めに任意のベクトル ½ ¼ を取り É からそのスカラー まず，一般に有限体 倍を一つにまとめた É É の部分集合を ×½ とすると、É の非ゼロ元は Õ ½ 個であるから ×½ Õ ½ で ある。×½ に属さない任意のベクトルを ¾ ¼ として、その非ゼロスカー倍をまとめたものを ×¾ とする Õ ½、これを続けて Ð 個の部分集合ができたとすると × × ´ µ であるから と同様に ×¾ Ð ¢´Õ ½µ 定義 ½¾ Õ ½、右辺で ½ したのはゼロベクトルを除いたためである。したがって、Ð ´Õ ½µ ´Õ ½µ とする。有限体 Õ 上の ´Ò Ò µ ハミング符号 ´À ÑÑ Ò のパリティ検査行列の縦ベクトルの任意の ¾ 本が Õ 上一次独立のものをいう。 Ò ハミング符号は ´ À ½ ¾ Õ 上の 次元の縦ベクトルで互いに一次独立な最大の集合 ½ ¾ Ò µ をパリティ検査行列とする符号である。符号語の集合 は，方程式 ´Õ ½µ ´Õ ½µº Ó Ò Ì À µ とは、そ を選んで、 Ç の解ベ クトルの集合である。さらに、ハミング符号では上記で説明したようにシンドロムがパリティ検査行列の列 番号に対応しているから、任意の ½ 個のエラーが簡単に訂正できることもいえる。 定理 証明 ハミング符号は最小距離が ¿、½ß ハミング符号 の完全符号である。 のパリティ検査符号を ´ À とする。但し、 の縦ベクトルと、任意の ¾ つは一次独立、である。符号語 ´成分 Ò 個の横ベ は長さ クトルµ は方程式 À で定められる。解を Òµ ½ ¾ ´ ½ ¾ Ì ¼ Ò µ とすると、 ½ ½ · ¾ ¾ ·¡¡¡· Ò Ò ¼ ¼ であるから一つを除 をみたす。自明な解を除いて、この関係を満たす最小ウェイトの解を求めると、 いて残りが全て ¼ という解はない。また，¾ つを除いて残りが全てゼロという解を ¼ ¼´ µ · ¼ となり、これは が一次従属であることを表すからハミング符号のパ リティ検査行列の選び方に反する。これより、最小距離、最小ウェイトは ¿ 以上であり，実際に ¿ 個のベ クトルが一次従属でハミング符号の条件を満たすパリティ検査行列ができる。 次に を ´Ò Ò µ ハミング符号とすると Ò ´Õ ½µ ´Õ ½µ である。 に対し、この符号語を中心 にして半径が ½ の球内の ÉÒ の個数は とすると、これは ½´ 一方、 Õ µ ½ · Ò´Õ ½µ Ò であるから Õ Ò ¢ Õ Õ Ò ½ · ´Õ ½µ ´Õ ½µ ¢ ´Õ ½µ É Õ Ò º したがって、 の元から長さが ½ の球を描くと の元が全て数え上げられるのでこの符号は完全符号である。 これらのことを合わせるとハミング符号は全ての受信語が訂正できる ½ß ½¼ Ò É であることがいえる。 例 ´½µ ¾ の場合 Õ ¾ ならば Ò ´¾¾ ½µ ´¾ ½µ ¿ したがって ´Ò Ò イ ¿ ならば Ò ´¾¿ ½µ ´¾ ½µ したがって ¾ 元 ´Ò 存在する。よく使用されるパリティ検査行列は ア ¼ À ½ ¼¼¼½ ½½½ ¼½½¼ ¼½½ ½¼½¼ ½¼½ À ´¿ ½ ¿µ であるから非実用的 ¿µ ´ ¿µ ハミング符号が ¼ ½ ¼¼½ ¼½¼ ¼½½ ½¼¼ ½¼½ ½½¼ ½½½ Ì 上で説明したようにウェイト ½ の誤り系列ベクトル ¿µ Ò に対し、シンドロム À Ì は À の第 列 ベクトルの転置ベクトル ´行ベクトルµ のスカラー倍が現れるが、Õ ¾ であるから列ベクトルが でゼロベクトルを 除くと ½ から までの ¾ 進数表示と一致する。このことを利用して ½ から までの列ベクトルを 順に並べてパリティ検査行列を作ると、 ウェイト ½ のシンドロムの ½ の位置が ¾ 進数で表示さ Ì れるようになっている。例えば、 ´¼¼¼½ ¼¼¼µ のとき × À ´½¼¼µ、これは ¾ 進数の º 他のパリティ検査行列 À と対応する生成行列 の例は そのまま現れる。さらに、成分の個数が ¿、成分が ¾ 元数の一次独立は ¾¿ ¼ ¼ ½ ¼½½½ ½¼¼ ½¼½½ ¼½¼ ½½¼½ ¼¼½ À ¼ これは組織的なハミング符号を与える。さらに À ½ ½¼¼¼ ¼½½ ¼½¼¼ ½¼½ ¼¼½¼ ½½¼ ¼¼¼½ ½½½ ½ ½¼¼½ ½½¼ ¼½¼¼ ½½½ ¼¼½½ ½¼½ により巡回ハミング符号を作ることができる。なお、これらのハミング符号はいずれも等価で ある。 ウ ´¾µ Õ ´Ò ´¾ ½µ ´¾ ½µ ½ であるから ¾ 元 ´½ ½½ ¿µ ハミング符号が存在する。 検査行列の列ベクトルは ½ から ½ までの ¾ 進数に対応している。 ならば ¿ 即ち Ò ¿µ É Ò ¼ ½ ¾ の場合 ¿ とすると Ò ´¿¿ ½µ ´¿ ½µ ´½¿ ½¼ ¿µ ハミング符号が存在する。パリティ検査行列を ¼ À ½ ½½½½½ ½½½¼¼ ½¼¼ ¼¼½½½ ¾¾¾½½ ¼½¼ ½¾¼½¾ ¼½¾½¾ ¼¼½ ½½ ½¿ であるから ¿ 元 ¼ とすると対応する生成行列 ½ は組織的なハミング符号を与える標準形をしている。 ½¼¼¼¼ ¼¼¼¼¼ ¾¼¾ ¼½¼¼¼ ¼¼¼¼¼ ¾¼½ ¼¼½¼¼ ¼¼¼¼¼ ¾¾¼ ¼¼¼½¼ ¼¼¼¼¼ ¾¾¾ ¼¼¼¼½ ¼¼¼¼¼ ¾¾½ ¼¼¼¼¼ ½¼¼¼¼ ¾½¼ ¼¼¼¼¼ ¼½¼¼¼ ¾½¾ ¼¼¼¼¼ ¼¼½¼¼ ¾½½ ¼¼¼¼¼ ¼¼¼½¼ ¼¾¾ ¼¼¼¼¼ ¼¼¼¼½ ¼¾½ 定義 Ò ½¿ を奇数として ´Ò ·½ 行 Ò µ 線型符号 ¼ · ½ 列の行列 À ¼ À ½ をパリティ検査行列とする ´Ò · ½ がのパリティ検査行列を ½ ¼ ¼ ºº º ¼ ½ ½ µ 線型符号 À ¼ を ´ ½ ¾ を奇数とするとき，¾ 元 ´Ò 定理 ¼Ì 証明 小距離 ½ の拡大線型符号という。 と Ò Ò·½ µ ´ ½ ¾ µ 線形符号 行 Ò 列µ とするとき， ½ ºº Ì À º ½ ¼ ¼ ½ 示すると ¼ ´ À Ò Òµ ¾ Ò·½ かつ の拡大線型符号 ¼ の違いを成分で表 ¼ ½ ¼ は ´Ò · ½ · ½µ 符号である。 ¼ のウェイトは偶数で，従って最小距離も偶数である。 の最小距離 は奇数であるから， ¼ の最 ¼ は偶数である。成分を ½ 個付け加えても距離は最大 ½ しか増えないので ¼ · ½ である。 系 ½ 拡大ハミング符号は ½ß 例 パリティ検査行列 ，¾ß 符号である。 ¼ À による ´ ¿µ ハミング符号と ´ ¼ ½¼¼ ¼½¼ ¼¼½ ½½½ ½ ½½½¼¼ ¼½½½¼ ½½¼½¼ ½½½½½ µ 拡大ハミング符号の符号語は次の通り ½¾ ´ ¿µ ハミング符号 ¼¼¼¼¼¼¼ ½½½¼½¼¼ ¼½½½¼½¼ ¼¼½½½¼½ ½¼¼½½½¼ ¼½¼¼½½½ ½¼½¼¼½½ ½½¼½¼¼½ ½½½½½½½ ¼¼¼½¼½½ ½¼¼¼½¼½ ½½¼¼¼½¼ ¼½½¼¼¼½ ½¼½½¼¼¼ ¼½¼½½¼¼ ¼¼½¼½½¼ ´ µ 拡大ハミング符号 ¼¼¼¼¼¼¼¼ ½½½¼½¼¼¼ ¼½½½¼½¼¼ ¼¼½½½¼½¼ ½¼¼½½½¼¼ ¼½¼¼½½½¼ ½¼½¼¼½½¼ ½½¼½¼¼½¼ ここに示した ´ ½½½½½½½½ ½½½½½½½½ ½¼¼¼½¼½½ ½½¼¼¼½¼½ ¼½½¼¼¼½½ ½¼½½¼¼¼½ ¼½¼½½¼¼½ ¼¼½¼½½¼½ ¿µ ハミング符号はこの後に説明する巡回符号の例でもある。´ は巡回符号ではない。 µ 拡大ハミング符号 数学の準備 ´¾µ 次の節で使う数学の道具の説明をする。 定義 ½ ´½µ 集合 Ê が加法に関して群，乗法に関して半群で加法と乗法に関して分配法則が成立するとき環 ´Ö Ò µ という。 ´¾µ 環 Ê の部分集合が Á イデアル ´ е とは，加法に関して部分群で，ÊÁ Á であるものをいう。 例 ´½µ 整数の集合 ，正方行列の集合， を体として 係数の多項式 Ü 等は環である。それぞれ有理整 数環，行列環，多項式環と呼ばれる。 ´¾µ の部分集合で Ò ¾ に対して ¼ ¦Ò ¦¾Ò ¦¿Ò はイデアルである。このイデアルは Ò また は ´Òµ と表される。 ´¿µ 多項式環 Ü の部分集合で ´Üµ ¾ Ü に対して ´Üµ で割り切れるもの全体はイデアルである。こ のイデアルは ´ ´Üµµ と表される。 定義 ½ ´½µ 上の例のように環 Ê の要素 Ô ¾ Ê の倍数の集合 ÔÊ ÔÜ Ü ¾ Ê で作られるイデアルを単項イデ アルまたは主イデアル ´ÔÖ Ò Ô Ð Ðµ という。 ´¾µ 環 Ê の任意のイデアルが単項イデアルのときに Ê は単項イデアル環 ´ÔÖ Ô Ð Ð Ö Ò µ であると いう。 ´¿µ イデアル Á において ¾ Á µ ´ ¾ Á ÓÖ ¾ Áµ が成り立つとき素イデアル ´ÔÖ Ñ Ðµ という。 ´ µ 環 Ê のイデアル Á が極大イデアル ´Ñ Ü Ñ Ð Ðµ とは，Á Ë Ê となるイデアル Ë があれば Ë Á または Ë Ê となるものをいう。 ´ µ 極大イデアルが唯一つしかない環を局所環 ´ÐÓ Ð Ö Ò µ という。 ½¿ 例½ の元 Ô ¾ ½ において · ´ÑÓ Ôµ ´ÑÓ Ôµ と する演算により環を作る。この環を Ô または ´Ôµ と表し，剰余 ´類µ 環 ´Ö × Ù Ð ´ Ð ××µ Ö Ò µ という。 ´Üµ 多項式環においても， ´Üµ ¾ Ü を一つ定め， ´Üµ より次数の低い Ü の元全体の集合に ´Üµ· ´Üµ ´ÑÓ ´Üµµ， ´Üµ ´Üµ ´Üµ ´ÑÓ ´Üµµ により和と積を定義したものを Ü ´ ´Üµµ と表し，剰余多項式 環 ´Ö × Ù Ð ÔÓÐÝÒÓÑ Ð Ö Ò µ という。 有理整数環 ´Ôµ 定理 略証 Ü Ü を取り ¼ ½ ¾ Ô ´ ´Üµµ は単項イデアル環である。 の場合だけ証明しておく。他の場合も同様にできる。 の任意のイデアル Á を考え，その元で正数のもので最小のものを Ô · Ö ´¼ Ö Ôµ となる Õ Ö が存在する。イデアルの定義より Ö × ÔÕ 正数のもので最小のものであったから Ö ¼ 即ち × ÔÕ が成り立つ。 ÔÕ ¾ Á に対し × ¾ Á がいえるが Ô は Á の元で とする。 × 巡回符号 º½ 定義 バースト誤りに強い符号の説明をする。 定義 ½ 線形符号 が次の性質を持つとき巡回符号という。 ´ シフトを続けると ´ ·½ ¼ ½ ½ µ ¾ ´ Ò ½ µ ¾ ¼ ½ µ ´ Ò ½ Ò Ò ¾ µ ¾ ¼ ½µ がいえる。巡回符号の場合は生成行列でその性 質を考えると少し表現が煩雑になるので別の表現方法を考える。 º¾ 符号の多項式表現 次の対応によりベクトルと多項式を関連づける。 ´ この対応で符号 ¼ ½ Ò ¾ Ò ½ ¾ Ò ½ µ ¾ Õ ´µ ¼ · ½ Ü · ¾ Ü · ¡ ¡ ¡ · Ò ½ Ü Õ に対応させた多項式全体の集合も同じ記号 Ü ´ÜÒ ½µ で表す。 Ò の中の線形符号 が巡回符号であるための必要十分条件は， が剰余多項式環 Õ Õ の中で，イデアルであることである。 定理 Ü ´ÜÒ ½µ 証明 Ò は線 ´ µ 多項式 が Õ Ü ´ÜÒ ½µ のイデアルであるとすると，まず加法部分群という条件から Õ ¾ Ò ½ 形部分空間であることが分かる。次に ´Üµ · Ü · Ü · Ü ¾ と任意の多項式の積が ¼ ½ ¾ Ò ½ ¾ Ò ½ · Ò ¾ Ò ½ に入ることから Ü ´Üµ ¼ Ü · ½ Ü · ¡ ¡ ¡ · Ò ¾ Ü Ò ½ Ü Ò ½ · ¼ Ü · ½ Ü · ¡ ¡ ¡ · Ò ¾ Ü ´ÑÓ ÜÒ ½µ ¾ であるから ´ Ò ½ ¼ ½ Ò ¾ µ ¾ º よって は巡回符号である。 ½ Ò が巡回符号であるとすると， ´Üµ ¾ に対し Ü ´Üµ ¾ º 繰り返して Ü ´Üµ ¾ ´ ´¾µ 逆に Õ ½ ¾ µ，この性質と線形性から任意の多項式 ´Üµ に対し ´Üµ ´Üµ ¾ であるから はイデアルで ある。 Ò Õ Ü ´Ü ½µ は単項イデアル環であることから はある多項式 ´Üµ の倍数となっている。この多項式 は巡回符号の多項式の中で最高次の項の係数が ½ のものを選べば良い。この多項式を巡回符号の生成多項 式 ´ Ò Ö ØÓÖ ÔÓÐÝÒÓÑ Ðµ とよぶ。 生成多項式 ´Üµ は ÜÒ ½ の因子である。何故ならば，ÜÒ ½ ´ÜµÕ ´Üµ · ִܵ ´¼ ´Ö´Üµµ ´ ´Üµµµ において ÜÒ ½ を法として考えると ִܵ ¾ であり， ´Üµ の次数は の中で最低次のもので あったから ִܵ ¼ これ以降は既約因子による因数分解 ÜÒ ½ る。この条件から Ò Õ Ø ´Üµ において重複する因子がないものとす の任意の組み合わせに対して巡回符号が存在するとは限らないことに注意しよう。 既約因子による因数分解 ÜÒ ½ ½ ´Üµ ¾ ´Üµ にµ 適当に選んで巡回符号の生成多項式 ´Üµ て ´Üµ を生成多項式として，長さ ½ ´Üµ ¾ ´Üµ Ø ´Üµ の因子 ½ ´Üµ ¾ ´Üµ ½ ´Üµ ¾ ´Üµ × ´Üµ を考える。 の情報記号系列を長さ Ò Ø ´Üµ から ´重複無し ´ ´Üµµ Ò とし の符号語に変換するには次のようにすれば 良い。 ´½µ ´¾µ ´¿µ ´ ¼ ½ ½ µ を情報記号系列とする。 ½ を対応させる。 に対し ½ 次の多項式 ´Üµ ¼ · ½ Ü · ¡ ¡ ¡ · ½ Ü Ò ½ を計算し ´Üµ に対し ´Üµ ´Üµ ´ ¼ ½ ¼ · ½ Ü · ¡ ¡ ¡ · Ò ½ Ü Ò ½ µ を符号語とすれば よい。 ¾ 元 ´ µ 巡回符号を考える。¾ 元体における既約因子への因数分解 Ü ½ ´Ü · ½µ´Ü¿ · ܾ · ´ ¼ ½ ¾ ¿ µ に対する ½µ´Ü¿ · Ü · ½µ から ´Üµ ´Ü¿ · ܾ · ½µ を生成多項式とすると，情報記号系列 ¾ ¿ ¾ ¿ ¾ 符号 は ´ ¼ · ½ Ü · ¾ Ü · ¿ Ü µ´½ · Ü · Ü µ ¼ · ½ Ü · ´ ¼ · ¾ µÜ · ¡ ¡ ¡ · ´ ¾ · ¿ µÜ · ¿ Ü より ´ ¼ ½ ´ ¼ · ¾ µ ´ ¾ · ¿ µ ¿ µ となる。この式より分かるように、得られた符号語は非組織的であり， これから情報信号系列を見るのは容易でないので次のように生成多項式を変更する。 例 次の多項式で，情報 記号系列の多項式が ½ 次の多項式であるから，Ò 次から Ò ½ 次の項まで 個の項が空いている ことを利用して情報記号系列を空いているところへシフトしてしまおうというものである。詳しい計算は 次のようにする。 組織的巡回符号の生成多項式 符号語を組織的にするアイデアは生成多項式が Ò ´½µ 情報記号系列の多項式を ´Üµ に ÜÒ をかける。この演算で情報記号系列は ÜÒ 次以上の項へシ フトされる。 ´¾µ ´ÜµÜÒ を ´Üµ で割り，商と余りを Õ ´Üµ ִܵ とすると ´ÜµÜÒ ´ÜµÕ ´Üµ · ִܵº ִܵ を右辺 Ò へ移項して ´Üµ ´ÜµÜ ִܵ ´ÜµÕ ´Üµº ´¿µ 巡回符号の性質から ´Üµ は巡回符号で，余りの性質から ´Ö´Üµµ ´ ´Üµµ Ò º したがっ Ò て，左辺の Ò 次以上の項は ´ÜµÜ の Ò 次以上の項と同じであるから、情報記号系列が保 存されている。 ½ ¿ · ¾ ܾ · ¿ Ü¿ µÜ¿ ¼ Ü · ½ Ü · ¾ Ü · ¿ Ü これを ´Üµ Ü¿ · ܾ · ½ で割ると ִܵ ´ ¼ · ½ · ¿ µÜ¾ · ´ ½ · ¾ · ¿ µÜ · ´ ¼ · ½ · ¾ µ となるから従って ´´ ¼ · ½ · ¿ µ´ ½ · ¾ · ¿ µ´ ¼ · ½ · ¾ µ ¼ ½ ¾ ¿ µ で後の 桁が情報記号系列，前の ¿ 符号語は 桁がパリティ検査部を表している。´最後の計算は ÑÓ ¾ で行っている。µ 上の例で続けると ´ÜµÜ 例 º¿ ´ ¼ · ½Ü 生成行列と検査行列 È È Ò とする。情報記号系列 ´Ò µ 符号 の生成多項式を ´Üµ ´ ¼ ½ ¼ · ½ Ü ·¡ ¡ ¡· Ò Ü Ò ½ Ð ½ 情報記号多項式 ´Üµ に対して符号語多項式が ´Üµ ´Üµ ¼ · ½ Ü ·¡ ¡ ¡· ½ Ü Ð ¼´ 従って符号語は Û ´ ¼ ¼ ´ ½ ¼ · ¼ ½ µ の生成行列は ½ Ò µ であるから Û ¼ ¼ ½ ¼ ¼ ¼ ¼ ¼ Ò Ò ¼ ¼ ½ Ò ¼ ¼ ¼ ½ ¼ ¼ ¼ Ò Ü で ´Üµ ´Üµ ´Üµ は ÜÒ ½ の因子であるから ´Üµ ¼ · ½Ü · ¡ ¡ ¡ · ものがある。このとき ¼ Ð · ½ Ð ½ · ¡ ¡ ¡ · Ò Ð Ò· ¼ ´ ÓÖ Ð ¼ ½ ¼ ¼ ¼ À ¼ ¼ ºº º ¼ ½ ½ とおくと À Ì となる。従って，符号語 Ç Û ½ ¼ ¼ ¼ ºº º ¼ ¼ ¼ に対し ½ ¼ ½ µ の Ð Ð µÜ ÛÀ Ì Ç ½ Ò ½ ´Ò Õ Ü Ò Ü µ となる ½µº º 即ち，À は符号 のパリティ 検査行列である。 これを多項式に置き換えると，۴ܵ ´Üµ 査多項式 ´Ô Ö ØÝ ´Üµ ´Üµ ´Üµ ¼ が成立する。従って， ´Üµ をパリティ検 ÔÓÐÝÒÓÑ Ðµ という。 À 符号 巡回符号の中で実用上重要な符号が により発見された。彼らに因んで パリティ検査行列とウェイト Ó× と Ê Ýß Ù ÙÖÙ ´½ À 符号と呼ばれる。 この式は À は À ´ ½ ¾ Ñ´½ パリティ検査行列とウェイトの関係を調べよう。パリティ検査行列を ´ À とする。ただし， ¼µ，それとは別に ÀÓ ÕÙ Ò の第 列ベクトル ´Ò Òµ ¾ ´µ À Ì ½ ¾ Òµ 次ベクトルµ を表す。このとき ¼ ´µ Ì· Ì Ì ¾ ¾ ·¡¡¡· Ò Ò ½ ½ の列ベクトルに関する一次従属関係を表している。 ½ ¼ µ ´Ò µ 線形符号 のパリティ検査行列 À の列ベクトルの ½ 個の任意の組み合わせは一次独 立であり， 個の組み合わせで一次従属となるものがある。 定理 ´ µ とすると， Ü ¾ ÉÒ Û Ø ´Û´Üµ µ であれば Ü ¾ であるから， ½ ¾ Ò の任 意の ½ 個の組み合わせは一次独立であることと同値である。 一方，条件から ¾ ´Û Ø Û´ µ µ であるから ¼ の成分を用いて À の列ベクトルの一次従属 の関係式が得られるので，定理がいえる。 証明 Û ウェイトが のベクトルが全て符号語であるとは限らないから，この定理で等号はいえない。一方，パリ ティ検査行列からウェイトを考えると次のようになる。 定理 ½¼ À 立で，ある Ò の ½ 個以下の列ベクトルの任意の組み合わせが常に一次独 個の組み合わせで一次従属になるならば，Û´ µ である。 の列ベクトル ½ ¾ ½ 個の組み合わせが一次独立ならば上の関係を成立させる組み ´ ½ ¾ Ò µ が存在しない。即ち， Ì Ì Û ´Üµ ½ ならば Ü ¾ º もし， 個の組み合わせで一次従属になる関係式を ½ ½ · ¾ ̾ ·¡ ¡ ¡· ¼ とすると ´¼ ¼ ½ ¼ ¼ ¾ ¼µ とすれば À Ì Ç 即ち ¾ Û Ø Û´ µ である。 証明 この定理の条件で Ê Ò ´À µ ½ まではいえるが， 個のある組み合わせが一次従属でも全て 個の組 み合わせが一次従属とは限らないので，等号はいえない。 定義 ½ 自然数 Ò Ð に対して ½ の原始 Ò 乗根を ¬ とし ¬ Ð ¬ з½ ¬ Ð·Æ ¾ ´Üµ とする。多項式 Ð·Æ ¾ の最小多項式を Ñ ´Üµ Ð Ñ Ð·½ ´Üµ Ñ ´Üµ を生成多項式とする Õ 上の長さ Æ µ という。 通常は Ò 定理 Õ Ð Äº ºÅº´ÑÐ ´Üµ Ò Ð·½ ´Üµ Ñ Ñ の巡回符号を設計距離 Æ の ½ とするが，強調する場合は狭義の ´Ò ÖÖÓÛß× Ò× µ Ñ ½ ´º ¬ À Æ ¼ の ½ ½ ºº º ½ Õ ¡ ¡ À 符号 ´ ¬ ¬ Рз½ ºº º Ð · Æ ¾ ¬ ¬ ¬ Ð ¾ ¡ ½ ¡ ¡ ºº º Ð · Æ ¾ ¬ で与えられる。 ½ Ð Ò ½ з½ Ò ½ ¬ з½ ¾ ¡ ¬ ºº ¾ º Ó × Ò À 符号という。 À 符号のパリティ検査行列は 元 À Ó À 符号 ´ÔÖ Ñ Ø Ú が ÕÑ の原始根µ であるとき，原始 ½½ 符号長 Ò，設計距離 Ð·Æ ¾ ´Üµµ ºº º ¬ Ð·Æ ¾ Ò ½ À Ó µ という。 ×Ø Ò ´ µ は情報記号系列多項式 Ú ´Üµ に対し ۴ܵ ¾ Ò ½ と置くと定義から Û¼ · Û½ Ü · Û¾ Ü · ¡ ¡ ¡ · ÛÒ ½ Ü 証明 符号語 ´ µ Û Ü ´ µ Û ¬ Û¼ · Û½ ¬ · Û¾ ¡ ¾ ¬ したがって Ò ½ µ´½¬ ´Û¼ Û½ Û¾ が Ð Ð ·½ Ð Û ¾ ¬ · Æ ¾ に対して成立する。行列 À Ò ½ ¬ Ü ´ µ ´¬ µ ¼ Ú ¬ Ò ½ Ì µ ¬ ¼ を定理のように定めると，この関係は次のように なる。 Ò ½ µÀ ´Û¼ Û½ Ú Ü ¡ ¡ ¡ · ¡ ¡ ¡ · ÛÒ ½ Ò ½µ で与えられる。 ´ µ ´Üµ ´ÑÓ Û Ü Û Ì ¼ したがって，À がパリティ検査行列である。 定理 証明 ½¾ 設計距離 Æ の À 符号の最小距離は Æ 以上である。 定理 ½¼ から，定理 ½½ で求めた Æ ½ 行 Ò 列のパリティ検査行列から任意の Æ ½ 列 を取り出してそ の組みの一次独立性をいえば良い。正方行列の一次独立性はその行列式の値が ¼ でないことをいえばよい。 ¬¬¬ ¡ ¡ ¡ ¬¬¬ ¡ ¡ ¡ ¬¬¬ ¬¬ ¡ ¡ ¡ ¬¬¬ ¬¬¬ ¡¡¡ ¬¬¬ ¡ ¡ ¬ ¡ ¡¡¡ ¬ ´ Æ ½ µ ½ ¾ ¬ Ð ½ з½ ºº º Ð · Æ ¬ ¬ ½ ¾ ¬ ½ Ð ¾ з½ ºº º Ð · Æ ¬ ¬ ¾ ¬ ºº ¬ ½ ¬ ¬ д ½ · ¾ · · Æ ½ µ ¬ ¬ д ½ · ¾ · · Æ ½ µ ÖÑÓÒ ¬ ¬ Æ ¾ × × Ø ¼ 最後の行列式は Î Ò ½ Æ ½ з Æ ¾ Æ ½ ½ ½ ºº º з½ ºº º º ¾ ¾ Æ ½ Ð ¬ ºº º ¬ ¾ Æ ¾ ¬¬¬ ¬¬¬ ¡ ¬¬¬¬ ½ ¾ ºº ¬¬¬ ¬¬¬ ¬¬¬ ¬¬ ¬ º Æ ½ ºº º ¬ Æ ½ Æ ¾ Ø の行列式と呼ばれている。 ´ µ ½ · Ü · Ü としたとき，符号長が ¿ の全ての ¾ 元 符号の生成多項式を次の表にあげる。この表より，例えば，´ ¿ µ 原始 À 符号の生成多項式 は 例 ¾ 上の原始元 « ¿ ´Üµ の最小多項式を ѽ Ü Äº ºÅº´Ñ½ ´Üµ ´ µ Ñ¿ Ü Ñ ´Üµµ ¾ ´½ · Ü · Ü µ´½ · Ü · Ü · Ü · Ü µ´½ · Ü · ܾ · Ü · Ü µ ½ · Ü · ܾ · Ü¿ · Ü · Ü · Ü · ܽ · ܽ · ܽ · ܽ ½ À ¿ ´Üµ 符号長 ¿ のすべての ¾ 元原始 Ò ¿ ½ ¾ ¿ ½ ¿ ¿ ¿¼ ¾ ½ ½ ½¼ ½ ´Üµ ¾ ´Üµ ¿ ´Üµ ´Üµ ´Üµ ´Üµ ´Üµ ½¼ ´Üµ ½½ ´Üµ ½¿ ´Üµ ½ ´Üµ ½¼ ½½ ½¿ ½ 共役元 ¿ ¾ « « « « « « « « ½½ « ½¿ « ½ « ¾½ « ½¾ ½¼ ¾ ¾¼ ¾ ¾ ¿¼ « « « ½ « « ¾ « « ¾ « « « ¼ « ¼ « « « ½ ¼ ½ Ñ¿ Ü ¿ ¿ « « « « « « ¿ « ¿ « « ½ ¿ « ¾ ¾ « ¿ « « ¾ « ½ ´ µ ´ µ Ñ ´Üµ Ñ ´Üµ Ñ ´Üµ ѽ½ ´Üµ ѽ¿ ´Üµ ѽ ´Üµ Ѿ½ ´Üµ Ѿ¿ ´Üµ Ѿ ´Üµ Ñ¿½ ´Üµ ѽ Ü ¿¿ « ¿ « ¾ ¿¾ « ¾¾ « « « « « « ½ « « « ½ ¾¿ « ¿½ « ½ « « « « ½¼ « ½·Ü·Ü ¾ ½ ´Üµ´½ · Ü · Ü · Ü · Ü µ ¾ ¾ ´Üµ´½ · Ü · Ü · Ü · Ü µ ½ ´Üµ ¿ ´Üµ ´Üµ´½ · ܾ · Ü¿ µ ´Üµ´½ · ܾ · Ü¿ · Ü · Ü µ ´Üµ´½ · Ü ·¿ ·Ü · Ü µ ´Üµ´½ · ܾ · Ü · Ü · Ü µ ¾ ½¼ ´Üµ´½ · Ü · Ü µ ½½ ´Üµ´½ · Ü · Ü · Ü · Ü µ ¿ ½¿ ´Üµ´½ · Ü · Ü µ の元の最小多項式 最小多項式 Ѵܵ ¾ « « À 符号の生成多項式 ´Üµ Ø « ¿ ½·Ü·Ü ½ · Ü · ܾ · Ü · Ü ½ · Ü · ܾ · Ü · Ü ½ · Ü¿ · Ü ½ · ܾ · Ü¿ ½ · ܾ · Ü¿ · Ü · Ü ½ · Ü · Ü¿ · Ü · Ü ½ · ܾ · Ü · Ü · Ü ½ · Ü · ܾ ½·Ü·Ü ·Ü ·Ü ½ · Ü · Ü¿ ½·Ü ·Ü 代数的復号法 復号法には最小距離復号法の他，確率的復号法と代数的復号法がある。最小距離復号法や確率的復号法は 全数検査が必要なので短い計算ではあるが指数関数の計算回数を必要とするが，代数的復号法は，例えば ¾ À 符号では Ç´Ò ÐÓ ¾¾ Òµ の演算回数ですむ。ただし，計算そのものはやや複雑である。以下において 代数的復号法を説明する。その要点は次の通りである。 元 ´½µ 受信語系列よりシンドロム多項式 Ë ´Üµ を計算する。 ´¾µ シンドロム多項式 Ë ´Üµ より誤り位置多項式 ´Üµ と誤り数値多項式 ´Üµ を求める。 ´¿µ ´Üµ より誤り位置を求める。 ´ µ ´Üµ と ´Üµ より誤り数値を求める。¾ 元符号の場合はこの計算はいらないのであるが，Õ 元符号 ´Õ を使用することによりバースト誤りの復号ができる。 ½ ¾µ 以下において Õ 上の長さ Ò，設計距離 ¾Ø · ½ の 項式 ´Üµ とする。次の記号を使う。 Ú 受信語系列 Û ´Üµ ´Üµ ɾ Ⱦ ´ ´ µ Û ¼ ´× ɾ Ø ¼ Ò 乗根，生成多 · Ú½ Ü · Ú¾ ܾ · ¡ ¡ ¡ · ÚÒ ½ ÜÒ ½ Û¼ Û Ü Ò ½ µ ° 誤り多項式 ´Üµ ¼ ½ × ¾ Ò ½ µ ° 受信語多項式 ½ とするµ，¬ を ½ の原始 Ú¼ Ú ´Û¼ Û½ 誤り信号系列 ½ Ò ½ µ ° 符号語多項式 Ú ´Üµ ´Ú¼ Ú½ 符号語系列 À 符号 ´Ð · Û½ Ü · Û¾ ܾ · ¡ ¡ ¡ · ÛÒ ½ ÜÒ ½ ¾ ½Ü · ¾Ü · · ¡ ¡ ¡ · Ò ½ ÜÒ ½ µ 誤り位置の集合 ´½ ¬ ܵ 誤り位置多項式 ¬ Ü ½º シンドロム多項式の計算 ´ Û ¬ µ ´ Ú ¬ ´½ ¬ ´ µ µ 誤り数値多項式 Ü ´ µ · ´Üµ に対して Û Ü Ú Ü µ · ´¬ µ ´¬ µ ´¬ µ · ´¬ µ ´¬ µ ´ ½ ¾ ¾Øµ であるからこの値は誤り系列にのみ依存しているのでシンドロムと名づけて良い。 ´ Ë とおくと誤り位置が ½ × ´× ¾ ½ ´¬ Ë µ Û ¬ ´¬ µ ´ ½ ¾ ¾Øµ µ なのでこの値は Ø µ½· ¾ ´¬ µ ¾ ·¡¡¡· × ´¬ Ð ½ ¾ µ× ¾ ´¬ µ 以下の計算で Ð Ð Ð とおくとシンドロムは ¬ × ´ Ð Ð Ë Ð ½ ´Ð ½ ¾ × µ ¾Øµ 次の式をシンドロム多項式という。 ´ µ Ë Ü Ë½ ¼ · ˾ Ü · Ë¿ ܾ · ¡ ¡ ¡ · Ë¾Ø Ü¾Ø ½ ¾Ø ½ ´¬ µ ¾ Ü ½ ¾ ½ ½ ½ «Ü ¬ ¾ ½ ¬ Ü ´ÑÓ Ü ½ ½ × ¾Ø Ð Ð ½ ½ ´«Üµ ¼ を利用して ´ µ ´¬ µ ½ ここで次の形式的べき級数展開 Ë Ü ¾Ø ¾Ø Ü ¾¼ µ × Ð ½ Ð Ð ½ ÐÜ ´ÑÓ ¾Ø Ü µ ÐÜ ½ ¾º 基本方程式の計算 誤り位置 ½ ´Üµ × を用いて次の式を定義する。 ¾ ´½ ¬ ½ ܵ´½ ´½ ½ ܵ´½ ¬ ¾ ܵ ´½ ¬ × Üµ ¾ ܵ ´½ × Üµ ½ ´¬ Ð µ ½ ´Ð ½ ¾ ¼ になる Ü は Ü ×µ であるか Ð ら，これより誤り位置が分かるからである。 ´Üµ をシンドロム多項式 Ë ´Üµ より求める方法を考える。 この式を誤り位置多項式と呼ぶ理由は ´Üµ ´ÜµË ´Üµ × Ð Ð ½ ÐÜ Ð ½ ´½ ½ ܵ´½ ¾ ܵ ´½ × Üµ ´½ ¾ ܵ´½ ¿ ܵ ´½ × Üµ ½ ½ ·´½ ºº º ½ ܵ´½ ¿ ܵ ´½ × Üµ ¾ ¾ ·´½ ½ ܵ´½ × × ´½ Ð Ð Ð ½ Ð ½ Ð ¾ ܵ ´½ × ½ ܵ × × Ü µ ´ÑÓ Ü ¾Ø ¾Ø ´ÑÓ ´ÑÓ Ü Ü ¾Ø µ µ µ 最後の式を ´Üµ とおき，誤り数値多項式と呼ぶことにする。 × ´Üµ 上の関係式 ´ÜµË ´Üµ ´Üµ ´ÑÓ × Ð Ð Ð ½ ¾Ø µ Ü Ð ½ Ð ´½ µ ´ÑÓ Ü ¾Ø Ü µ はある多項式 ´Üµ で次の様に表すことができる。 ´ÜµË ´Üµ · ´ÜµÜ¾Ø ´Üµ ´ µ と Ü¾Ø が既知で， ´Üµ ´Üµ ´Üµ は未知の多項式であるが，この関係式は Ë ´Üµ と Ü¾Ø の最大公約多項式が ´Üµ であることを表していて，これはユークリッド互除法 ´または互減法µ アルゴリズ ムを多項式に拡張した方法で高速に計算が可能である。 この関係式で Ë Ü ¿º 誤り位置の計算 基本方程式の計算により得られた ´Üµ のゼロ点を求めれば，その逆数が誤り位置を 示している。一般に方程式のゼロ点を求めることは非常に難しい問題であるが，今扱っている係数体は有限 Ò ½ を順に代入して行けば有限回で解を求めることが ¬ 体で ¬ が ½ の原始 Ò 乗根であるから，¬ ¬ ¾ できる。解は一つとは限らないから全てを試す必要がある。これを Ò 探索 ´ Ò × Ö µ という。 º 誤り数値の計算 最後に誤り数値を計算する。この計算は ¾ 元符号のときは不要であるが，Õ ¾ の符 号を使用することによりバースト誤りに強い符号が得られることになり，実用上も使用されている。 定理 ½¿ ´ ÓÖÒ Ý のアルゴリズムµ 誤り数値は次の式で計算される。 Ð ただし， Ð « Ð は誤り位置で Ð ´ Ð ½ µ ¼ ´ Ð ½µ Ò 探索でで求めた。また， ¼ ´Üµ は ´Üµ の形式微分を表す。 ¾½ 略証 誤り数値多項式は × ´Üµ でこれに × Ð Ð Ð ½ ´½ µ ¾Ø ´ÑÓ Ü µ Ü ½ Ð ½ を代入して Ð Ü × ´ Ð ½ µ Ð Ð ½ Ð µ ´½ ½ ¾Ø ´ÑÓ Ü µ Ð したがって Ð ´ Ð ½ µ × Ð ´ÑÓ ½ µ ´½ Ü ¾Ø µ ´½µ Ð ½ Ð 一方， ´Üµ を Ü で形式微分して ¼ ´Üµ ´ ½ µ´½ ·´½ ºº º ¾ ܵ´½ ½ ܵ´ ¿ ܵ ¾ µ´½ ´½ ¿ ܵ × Üµ ´½ × Üµ ·´½ ½ ܵ ´½ × ½ ܵ´ × µ × × ´½ ܵ Ð ½ Ð ½ Ð この式に ½ を代入して Ð Ü ¼ ´ ½ µ Ð Ð × ½ Ð µ ´½ ½ ´ÑÓ ¾Ø Ü µ ´¾µ Ð 式 ´¾µ を式 ´½µ に代入して定理の式を得る。 ½½ Ê ßËÓÐÓÑÓÒ 符号 À 符号の特別のものが Ê Ö Ô Õ ´Õ う。簡単にするために 定義 ´Üµ 定理 ½ É ½ ½ ´Ü ½ Ê « ßËÓÐÓÑÓÒ 符号で や Î の符号に用いられている。 ÔÖ Ñ µ 上の長さ Ò Õ ½ の原始 À 符号を Ê ßËÓÐÓÑÓÒ 符号とい Ð ½ として説明すると，Ò の原始 Ò 乗根の一つを « とするとき，生成多項式は µ になる。 Ô ßËÓÐÓÑÓÒ 符号の定数を ´Ò µ とすると ¾¾ Ò · ½ が成り立つ。 証明 巡回符号の生成多項式の所で，情報ベクトルの長さ，符号語ベクトルの長さをそれぞれ と，生成多項式 ´Üµ の次数は ，符号空間は ´Üµ Ü ´Üµ ´Üµ Ü ßËÓÐÓÑÓÒ 符号の場合， ´Üµ の次数は ½ であるから ½ 説明されている。Ê Ò Ò とする ½ ´Üµ を基底に持つことが ¾ Ü Ò が成立する。 ¾¼ ´Ò µ 符号で Ò · ½ の関係が成り立つときに最大距離分離符号 ´Å Ë Å Ü ÑÙÑ ×Ø Ò Ë Ô Ö Ð Ó µ という。Å Ë 符号では同一最小距離を有する符号の中で最小の検査記号数を持 つ符号である。 定義 例 ½¼ ´½ ½½ µ ÊË 符号を考える。生成多項式は ´Ü «µ´Ü «¾ µ´Ü «¿ µ´Ü « µ ´Üµ ½¼ « 情報多項式を ٴܵ ´ µ Ú Ü · «¿ Ü · « ¾ Ü · «½¿ Ü¿ · Ü · «Ü¾ · «¿ ܽ¼ とすると，符号語多項式 « ´ µは Û Ü ´ µ ´Üµ Ù Ü ½·« Ü ·« ¿ Ü · «½¿ Ü · «½ · «Ü · «½¿ ܽ¼ · « Ü ½½ Ü ·« Ü ½¾ · «Ü½¿ · «¿ ܽ ´« ¼«¼¼ ¼¼¼¼¼ «¿ µ に対して符号語系列が Ú ´½« ¼« «½¿ «½ «¼¼¼ «½¿ « « ««¿ µ となる。所で，実際のディジタル信号は É ¼ ½ で成り立っているのであるから， ¾ の元を ¾ 元ベク ¾ トルで表示すると次の表になる。即ち，« « は実際は ´¼¼½¼µ ´¼½¼¼µ の列に置き換えられて送信 される。従って，実際に送信される信号にバーストエラーが起きても ÊË 符号系列の方では，一つか二つの 符号語が失われただけを意味し，バーストエラーに強い符号ということになる。 即ち，情報記号系列 Ù ¾ の元の表現 ´最小多項式 Ü · Ü · ½µ ベキ表現 多項式による展開 ベクトル表現 ¼ ½ ¼ ½ « Ü ¼¼¼¼ ¼¼¼½ ¼¼½¼ ¼½¼¼ ½¼¼¼ ¼¼½½ ¼½½¼ ½½¼¼ ½¼½½ ¼½¼½ ½¼½¼ ¼½½½ ½½½¼ ½½½½ ½½¼½ ½¼¼½ ¾ ¾ « Ü ¿ ¿ « « « « « « « ½¼ « ½½ « ½¾ « ½¿ « ½ « Ü Ü Ü ·½ ¾ Ü ·Ü · ܾ ¿ Ü ·Ü ·½ ¾ Ü ·½ ¿ Ü ·Ü ¾ Ü ·Ü ·½ ¿ ¾ Ü ·Ü ·Ü ¿ ¾ Ü ·Ü ·Ü ·½ ¿ ¾ Ü ·Ü ·½ ¿ Ü ·½ ¿ Ü ¾¿ 例 ½½ 上の例を復号してみよう。この符号は ¾ß Û であるから受信語記号系列を ´½« ¼«½½ «½¿ « ½ ¼¼¼ « ¾ ¿ « « « «« µ とする。受信語多項式は ´ µ Û Ü ½·« Ü · «½½ Ü¿ · «½¿ Ü · «½ Ü · «Ü · «¾ ܽ¼ · « Ü ½½ ·« Ü ½¾ · «Ü½¿ · «¿ ܽ ½º シンドロムの計算 ¾ ´Üµ の根は « «¾ «¿ « であったからこれを順次 ۴ܵ に代入して ˽ Û ´«µ « ¸ ¾ ¿ ½¿ ¸ Ë ¾ ½¿ ܾ · « Ü¿ ˾ Û ´« µ « ¸ Ë¿ Û ´« µ « Û ´« µ « ¸ Ë ´Üµ « ·« Ü ·« ¾º 基本方程式の計算 Ü と Ë ´Üµ にユークリッドの互除法を用いて ´ÜµË ´Üµ · ´ÜµÜ ´Üµ を求めると， ´Üµ «¾ · « Ü， ´Üµ ½ · «½¾ Ü · «½¿ ܾ ¿º 誤り位置の計算 ¾ ½ を順次 ´Üµ に代入して ¼ になるものを求める。今の例では ´« µ « ´«½¾ µ ¼ ¾ の元 « « ½¼ ¸ « ½¾ ¿ ¿ ½¼ に誤りが起き であるから，これらの逆数を計算すると « « « º 従って，Û ´Üµ の Ü と Ü ている。 º 誤り数値の計算 始めに ´Üµ を形式微分して 生成多項式 ¼ ´Üµ ¾ ¢ «½¿ Ü · ½ ¢ «½¾ ½¾ ´ÑÓ ¾µ « 従って， « ¿ ½¾ « « ½¼ これより誤り多項式は ´Üµ « Ü ¿ · «½ ´«½¾ µ · «¾ ´« µ · «¾ « ½¼ Ü ½¾ « « ½ であるから復号語多項式は Ú ´Üµ 正しく復号された。 ¾ ´ µ ´Üµ Û Ü ´ µ より Ú Ü
© Copyright 2024 ExpyDoc
