代数符号

その他代数

基本的であるにも関わらず、用法がゆれている言葉達：

  1. 符号〈コード〉
  2. 記号〈シンボル〉
  3. ブロック
  4. 語〈ワード〉
  5. 符号長
  6. 列〈シーケンス | ストリング | ストリーム〉
  7. タプル、n-タプル
  8. q項〈q-ary〉
  9. a codeword of a code
  10. メッセージ
  11. パケット
  12. 情報
  13. データ

集合とその要素が曖昧にされがち：

  1. アルファベット Q と、その要素
  2. 直積空間 Qn と、その要素
  3. コード〈符号〉＝部分空間 C⊆Qn と、その要素＝符号語

なんて呼べばいいか分からない概念：

  • Qn→Qm の線形変換

本来の意味からは離れてしまった言葉：

誤り訂正のオモチャの例：

  • 文字列 例：ツクエ
  • 文字 'ツ', 'ク', 'エ'
  • さらに文字列の例： ツエク, クツエ、クエツ、エツク、エクツ
  • 文字の集合 Q = {'ツ', 'ク', 'エ'}
  • 長さ3の文字列の集合 = {ツツツ, ツツク, ... } 33 = 27個
  • 語の集合と非語の集合（word nonword, sentence nonsentence）
  • 誤り方は置換誤りだけと仮定 ラングドシャ → ランドグシャ, アニマル → アルマニ
  • 「クツエ」から置換で得られる語が元の語
  • 語と誤り語の区別ができるか？
  • 非語は誤り語で間違いない。
  • 語が誤り語になってしまう例。
  • ミルク、ミクル、ルクミ、ルミク、クミル、クルミ、
  • 距離にケメニー距離〈Kemeny distance〉

檜山の整理案：

集合 集合の要素 備考
アルファベット Q シンボル s∈Q Qの基数はq
タプル空間 Qn q{項|元}・nタプル x∈Qn nはタプルの長さ
コード C ⊆ Qn {コード}?語 c∈C Cの次元をk

線形符号では：

  1. Qは、q元体とする。
  2. タプル空間Qnは、体Q上のn次元ベクトル空間と考える。
  3. コードCは、親ベクトル空間Qnのk次元部分ベクトル空間。
  4. Qnの要素は、q{項|元}・n-タプルと呼ぶ。
  5. Cの要素は（長さnの）語と呼ぶ。
  6. Qn＼Cの要素は（長さnの）非語〈nonword〉と呼ぶ。長さとCの次元を混同しない。
  7. Qnは距離空間とする。その距離はδ(-, -)で表す。
  8. Qnには、ベクトル空間としてのゼロベクトルがあるので、w(-) := δ(0, -) を（{ベクトル | タプル}の）重さと言う。重さはノルムとは限らない、つうか、ノルムじゃない。

上記の C = (Qn, C) を線形コード〈符号〉と呼ぶ。線形コードのクラスをパラメータで分類する。

  • L-Cq(n, k, d)

CがクラスL-Cq(n, k, d)に属する線形コードだとは：

  • アルファベット Q ＝ ベクトル空間のスカラー体 の基数〈要素数 | 濃度 | 位数〉が q
  • タプルの長さ＝親ベクトル空間の次元が n
  • コードC（親ベクトル空間の部分空間）の次元がk
  • Cの異なる要素間の最小距離がd

クラスは、構造達の外延だから、構造そのものがちゃんと定義されないとクラスも曖昧になる。

リード／ソロモン符号のクラスを次のように書く。

  • RS-Cq(n, k)

リード／ソロモン符号では、dが n, k から決定されてしまう。

  • d = n - k + 1 （qに依存しない）

スカラー体が {0, 1}、親ベクトル空間は、{0, 1}n なら、タプルは2項n-タプル＝バイナリー・n-タプル。L-C2である符号を、バイナリー線形符号ともいう。バイナリー線形符号も構造のクラスの名前。

同義語や表記のゆれ：

  1. エンコード = エンコーディング = 符号化
  2. デコード = デコーディング = 脱符号化 = 復号化 = 復号
  3. コーディング = エンコーディング
  4. コーディング = (エンコーディング and/or デコーディング）
  5. コーディング = プログラム・ライティング
  6. コード = コーディング
  7. コード = コード語 = 語
  8. コード = 語空間 （語空間 ≠ タプル空間）
  9. コード = タプル空間（非語も含まれる）
  10. コード = プログラム・ソースコード
  11. ブロック = ブロック符号化（畳み込み符号化ではない）
  12. ブロック = タプル = ベクトル
  13. ブロック空間 = タプル空間 = ベクトル空間
  14. シンボル = アルファベットの要素 = 体の元 = スカラー
  15. シンボル = ビット （アルファベットが2元のとき）
  16. 体 = 有限体
  17. 体 = 素体 （単純体というべきだろうが、習慣で）

符号化と方式〈スキーム〉の分類

  1. 情報源符号化〈source coding〉
  2. 通信路符号化〈channel coding〉 通信路は記号的・代数的
  3. 伝送路符号化〈line coding〉 伝送路は物理的・幾何的

モジュレーション／デモジュレーション〈変調／復調〉は、伝送路符号化に入る。有限離散な構造を多様体（主にユークリッド空間）に写像するのがモジュレーターで、その像である離散集合はコンスタレーション。

別に暗号化と復号がある。暗号化は上のどの時点でも入る。

その他：

  • binary linear code = linear binary code = L-C2(n, k, d) クラスのコード
  • ternary linear code = linear ternary code = L-C3(n, k. d) クラスのコード
  • binary = ニ元 = ニ項
  • ternary = 三元 = 三項
  • binary field = 二元体
  • ternary field = 三元体
  • BCH-C, RS-C には、 Berlekamp-Massey (BM) decoding algorithm がある。