| sys.pdf sys-s.pdf sys.txt 記事一覧 |
 [4-32] ハミング距離 |
#45: 巡回符号
4 ビットのデータ a3a2a1a0 に対応する多項式 P(z) = a3z3 + a2z2 + a1z + a0 と多項式 G(z) = z3 + z + 1 の積を F(z) とします．この G(z) は z4 + 1 の因数なので zkF(z) mod (z4 + 1) も G(z) で割り切れます．したがって G(z) で割り切れる 6 次の多項式（係数は 7 個）の集合は巡回置換に対して不変となります．この集合が巡回符号です．個々の多項式（巡回符号の要素）を符号語，G(z) を生成多項式といいます．<--- 通常は z でなく x を使います（#33の両側 z 変換に記号を合わせただけ．解析接続は無関係．マネをしないこと）．
F(z) を送信したときに伝送誤りで F '(z) = F(z) + zp を受信したとすると F '(z) mod G(z) = zp mod G(z) ≠ 0 となり，伝送誤りが発生したことが分かります．また，符号多項式が 6 次で G(z) が原始多項式だから，単一誤りを仮定すると F '(z) mod G(z) （シンドローム）から誤りが発生した場所（ p の値）も分かるので誤りを訂正できます．
補足：（ブロック符号の場合は）符号語間のハミング距離でその符号の誤り検出・訂正能力を評価できます．巡回符号では生成多項式の次数を高くするとハミング距離の最小値が増加し，複数箇所の誤りも訂正できるようになりますが処理は面倒です．一方，誤りの検出は容易なので，誤った場合は再送を要求する方式も広く用いられています [4-41]．
[4-28] 巡回符号 - Wikipedia
http://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E7%AC%A6%E5%8F%B7
[4-32] ハミング距離 - Wikipedia
http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%B3%E3%82%B0%E8%B7%9D%E9%9B%A2
等しい文字数を持つ二つの文字列の中で、対応する位置にある異なった文字の個数である。
[4-33] ハミング符号 - Wikipedia
http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%B3%E3%82%B0%E7%AC%A6%E5%8F%B7
知られている誤り訂正符号の中では最も古く、ブロックあたり1ビットの誤りを訂正できる。
------------------------------
[4-34] 線型符号 - Wikipedia
http://ja.wikipedia.org/wiki/%E7%B7%9A%E5%9E%8B%E7%AC%A6%E5%8F%B7
符号化と復号が効率的
[4-35] 符号理論 - Wikipedia
http://ja.wikipedia.org/wiki/%E7%AC%A6%E5%8F%B7%E7%90%86%E8%AB%96
[4-36] 誤り検出訂正 - Wikipedia
http://ja.wikipedia.org/wiki/%E8%AA%A4%E3%82%8A%E6%A4%9C%E5%87%BA%E8%A8%82%E6%AD%A3
[4-37] ハミング限界 - Wikipedia
http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%B3%E3%82%B0%E9%99%90%E7%95%8C
[4-38] ギルバート＝バルシャモフ限界 - Wikipedia
http://ja.wikipedia.org/wiki/%E3%82%AE%E3%83%AB%E3%83%90%E3%83%BC%E3%83%88-%E3%83%90%E3%83%AB%E3%82%B7%E3%83%A3%E3%83%A2%E3%83%95%E9%99%90%E7%95%8C
[4-39] プロトキン限界 - Wikipedia
http://ja.wikipedia.org/wiki/%E3%83%97%E3%83%AD%E3%83%88%E3%82%AD%E3%83%B3%E9%99%90%E7%95%8C
[4-40] リード・ソロモン符号 - Wikipedia
http://ja.wikipedia.org/wiki/%E3%83%AA%E3%83%BC%E3%83%89%E3%83%BB%E3%82%BD%E3%83%AD%E3%83%A2%E3%83%B3%E7%AC%A6%E5%8F%B7
訂正能力が高く様々なディジタル機器等で応用されている。
[4-41] 巡回冗長検査 - Wikipedia
http://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E5%86%97%E9%95%B7%E6%A4%9C%E6%9F%BB
CRC-32-IEEE 802.3 は1975年に登場し、イーサネットなどの各種通信やZIPやPNGなど各所に使われている。
[4-42] 畳み込み符号 - Wikipedia
http://ja.wikipedia.org/wiki/%E7%95%B3%E3%81%BF%E8%BE%BC%E3%81%BF%E7%AC%A6%E5%8F%B7
デジタルラジオ、携帯電話、人工衛星リンク、Bluetooth などの実装について、性能を向上させるためによく使われる。
[4-43] ターボ符号 - Wikipedia
http://ja.wikipedia.org/wiki/%E3%82%BF%E3%83%BC%E3%83%9C%E7%AC%A6%E5%8F%B7
宇宙探査機での通信など、ノイズのある限られた帯域幅で情報転送量を可能な限り最大化したい場合に使われている。
[4-44] 誤り訂正符号
http://www.ohtsuki.ics.keio.ac.jp/pdf/class.pdf
[4-45] 同期方式 - Wikipedia
http://ja.wikipedia.org/wiki/%E5%90%8C%E6%9C%9F%E6%96%B9%E5%BC%8F