The Continuing Story of Error Correction Code 3
ハミング距離
カルノー図
カルノー図は論理式を簡略化するためなどに使用する図です。
このような論理式の簡略化を図から容易に行うことができます。
が、ここでは論理式は扱いません。ハミング距離の理解のためだけにカルノー図を使います。
ハミング距離の説明でよく超立方体が使われていますが（ハミング距離 - Wikipediaでも4次元の超立方体が使われてますね）次数が上がると図が意味不明になるし、そもそもイメージしずらいのでここではカルノー図で押し通してみましょう。
では、8変数までのカルノー図の作り方のはじまりはじまり・・・
2ビットのカルノー図
縦方向に、横方向に
を割り当てて、各マスには
の3ビットの値が書き込まれており、3ビットが取り得る値の一覧表になっています。 3ビットが取り得る値は
で4通りなので4種類の値となります。
2ビットのカルノー図はこれで完成です。
「で、カルノー図って一体なんなんだよ！！」
はい、そうでしたね。ではカルノー図が一体何なのかは3ビットのカルノー図で説明しましょう。
3ビットのカルノー図
縦方向に、横方向に
を割り当てて、各マスには
の3ビットの値が書き込まれており、3ビットが取り得る値の一覧表になっています。 3ビットが取り得る値は
で8通りなので8種類の値となります。
この表、縦方向のは
→
→
→
という順番に割り振ってありますが最後の2つ黄色の塗りつぶしの部分の順番を入れ替えて
→
→
→
としてみます。
このようにして作られた表には面白い性質があります。
からスタート、一つ下に進むと
になり
と比べると
だけが
から
に変化します。
から更に一つ下に進むと
になり
と比べると
だけが
から
に変化します。
から更に一つ下に進むと
になり
と比べると
だけが
から
に変化します。
更に一つ下に進めてみようかな、と思ったのですがもうこれ以上、下はないので先頭の行に戻るとになり
と比べると
だけが
から
に変化します。
ここでは上下に移動しましたが、左右の移動も変化するビットは1ビットだけになっています。
最初の表ではの下は
ですから
が
から
、
が
から
に変化しているので2ビット変化していますね。
このように上下左右とは1ビットしか異ならないように値を並べた表を「カルノー図」と呼びます。
表のはじまで行ったとき反対側に移動するのが面倒なら表自体を上下左右に伸ばして更に続きがあるんだ、と考えると簡単です。 下の表は中央、青塗りつぶしのまわりに同じ表をつなげてみました。
2ビットでは隣との違いは必ず1ビットとなるのでマトリクスにすると自然とカルノー図になっているんですね。
4ビットのカルノー図
4ビットのカルノー図は横方向も2ビット割り当てます。
値の並びは縦方向と同じく隣同士が1ビット違いになるようにします。
上下左右に移動したとき変化するビットは1ビットのみになっていますね。
5ビットのカルノー図
4ビットまでのカルノー図は上記のとおり容易に作成できますが、更にビット数を増やそうとするとちと面倒なことが起こります。
縦方向は→
→
→
→
→
→
→
と1ビットづつ変化するように配置して以下のような表ができます。
なにか、上手いことできているように見えますが黄色のセルを見てください。
と
なので1ビットしか変化していないのですが、隣同士ではないんです。
5ビットになると変化するビットは5個、移動方向も5個ないといけないのですが、移動方向は上下左右の4通りなのですからもう一つ、新しい移動方向を考える必要があるのです。黄色のセルはこの新しい移動方向で隣同士になる、ということになります。
新しい移動方向は
- 2行目と7行目
- 3行目と6行目
になります。
でも、なんか分かりづらいですね・・・
ということで少し考え方を変えてみましょう。上下左右の移動は2次元平面での移動ですから移動方向を増やしたければ3次元にしてやればよいのでは？
ということで、3次元バージョンの5ビットカルノー図です。
5ビットでは4ビットのカルノー図を2階建にします。移動方向は上下左右に加えて1階、2階を行き来できます。
5ビットのの
を1階、2階に割り当てて以下のようにしましょう。
1階
2階
先ほど、隣同士になっていなかったと
も1階と2階で隣どうしになれました。これで5ビットすべて隣は1ビット違いとなりました。
6ビットのカルノー図
ここまでの流れを考えれば6ビットは簡単ですね。
そうです、4階建てにします。
1階
2階
3階
4階
7ビット、8ビットのカルノー図
最後、7ビットと8ビット。7ビットなら移動方向は7種類、8ビットなら移動方向は8種類必要になります。
上下左右に上の階、下の階と3次元の移動方向は使い果たしてしまいました。
そこで建物を増築します。1号館、2号館と2棟構成にしたのが7ビット、1号館から4号館の4棟構成にしたのが8ビットのカルノー図になります。
移動方法は・・・、空間移動です。とある部屋から別の棟の同じ位置の部屋に移動することができます。
7ビットの棟構成
1号棟
2号棟
8ビットの棟構成
1号棟
2号棟
3号棟
4号棟
ここまでくると、論理式の簡略化としての用途には使いずらくなってきます。まぁ、頑張ればできますが普通は6ビットぐらいまででしょうか。
しかし、ここではハミング距離のイメージを掴むためにカルノー図を用いるので、このワンフロア16部屋、4階建て、4棟構成のカルノー図でも十分に使うことができます（たぶん・・・）
ハミング距離はどうしたんだよ・・・
はい、おまたせしました。
やっとここからがハミング距離の説明です！！
エラー検出・訂正で使用するハミング距離とは2つの値の異なるビットの数となります。
そしてカルノー図上では異なる部屋の間の距離となります。
この距離とは一般的な距離の測り方とは少し異なります。とある部屋から1ビットしか異ならない部屋への移動を1として最短で何部屋移動するか、が距離となります。
4ビットのカルノー図で考えてみましょう。
- 黄色の部屋
と緑色の部屋
のハミング距離は1
- 黄色の部屋
のハミング距離は2
- 緑色の部屋
のハミング距離は1
1はすぐ隣なのでから左に行って
で1、2は
から右に行って
、下に行けば
なので2、これはいいですね。
3はから右に行って
、更に右に行って
、もひとつ右に行って
だから3じゃないの・・・？と思うかもしれませんがカルノー図は左端と右端は繋がっているので
から左に行って
だから1になります。
この決まりは階の間の移動でも、棟間の移動でも同じです。
2階建ての5ビットカルノー図で試してみましょう。
黄色の部屋から緑色の部屋
までの距離は
から1階を右に行って
、更に右に行って
、下に行って
、もひとつ下に行って
、2階に上って
でハミング距離5となります。どのような経路を辿ってもこれより短い経路はありません。
実際にカルノー図を辿ってみてくださいね。
1階
2階
5ビットで全ビットが0だったのが全ビット1になったのだから異なるビットは5個でハミング距離は5、と見ただけでわかりますがこの後カルノー図を使ってエラー検出できる、できない、エラー訂正できる、できない、エラー検出・訂正ができるなら何ビットまでできるのか、の考察を行うので頭の中でカルノー図とハミング距離をイメージできるようにしておきましょう。
余談と次回予告
マンハッタン距離
カルノー図上でのハミング距離を数学用語で言うと『マンハッタン距離』となります。
一般の距離は『ユークリッド距離』と言って2点間を直線でつないだときの直線の長さとなります。これに対して『マンハッタン距離』は各座標軸での距離の和となります。マンハッタンの碁盤の目のような道路を進んでいったときの距離って感じですかね。斜めにショートカットすれば近いんだけどもそれはできない、碁盤の目を右に左に行った時の距離ということです。
ただ、マンハッタンの道路の右端と左端は繋がっていませんがカルノー図の右端と左端、上端と下端は繋がっているので計算するときはこれを考慮に入れる必要がありますね。
グレイコード
3ビットのカルノー図を作る際に→
→
→
という並びを使用しました。隣同士が1ビットしか変化しない並びです。
このようなコードをグレイコードと呼びます。5ビットのカルノー図を作る際に最初に考えた→
→
→
→
→
→
→
という並びも隣同士は1ビットしか変化しないのでグレイコードですね。
ソフトウェアではあまりお目にかかりませんがハードウェアではよく使う手法となります。
一度に複数のビットが変化すると回路を構成する部品の微妙な動作時間の違いから本来出力されるべきではないコードが一瞬みえてしまい、これが誤動作の引き金になったりします。ここでグレイコードを使うと変化するのは必ず1ビットですから部品の動作時間のバラツキに関わらず正しいコードしか出力されないことになります。
一見、複雑そうなコードの並びですが信頼性を上げる重要な手法なんですね。
超立方体
2次元の座標で正方形を考えます。頂点が4個あってそれぞれの頂点からは2本の同じ長さの辺が出ており頂点で直角に交わっています。
では3次元の座標で立方体を考えます。頂点が8個あってそれぞれの頂点からは3本の同じ長さの辺が出ており頂点で直角に交わっています。
では4次元の座標だったら？
2次元から3次元に拡張したとこと同じように3次元から4次元に拡張すると頂点が16個あってそれぞれの頂点からは4本の同じ長さの辺が出ており頂点で直角に交わっている、そんな形になりそうです。
でもこれ、3次元の座標では作ることはできないですよね。頂点から4本の辺が出ていてそれぞれが直角に交わっている、この時点で3次元では実現できません。この4次元、あるいはそれ以上の次元での立方体を超立方体といいます。
4次元なので2次元や3次元で作ることはできませんが、条件をゆるめれば図にすることはできます。たとえば頂点で各辺が直角に交わっている、各辺の長さは同じ、という条件を外して書いたのがハミング距離 - Wikipediaの図になります。
実はカルノー図を7ビットに拡張するときにも4次元をどう扱うか、という問題に直面しています。この時は隣の棟に空間移動できる、というズルをして解決しましたね。
次回予告
さて、ハミング距離もわかってきたので次回はエラー検出・訂正とハミング距離について考えてみましょう。
思考のサルベージ(その8)
各工程で心がけたい思想を掘り起こしてみる
今回は、設計工程における「過剰設計」について考えてみます。対向装置の挙動が不透明な状態で設計をすすめると、「過剰設計」になることがあります。「過剰設計」とその弊害とは一体何でしょうか。
準正常系の設計
以前にもお話させていただきましたが、規格に準拠する設計では、正常系、異常系は規格に沿った設計をしていればまず間違いありません。ただし、準正常系では、各メーカに設計がゆだねられることが多いです。 例えば、規格で以下のシーケンスが規定されていて、装置Aの設計をするとしましょう。
装置Bから装置Aに「特定のアクセスが一定回数」続いたら、
- １．装置Aが装置Bにデータ取得指示を出す。
- ２．装置Bは装置Aにデータ取得要求を出す。
- ３．装置Aは装置Bにデータを送信する。
装置Aは装置Bがデータを取得したと認識する。
正常系の設計は明快ですね。装置A、装置Bの間でやり取りされるメッセージのプロトコル違反は異常系に落とし込めます。
では、「１」のシーケンスが動いた後、「２」のシーケンスが動かなかった場合はどうしましょう？一見すると、装置Bが規格に沿った動作をしないケースとなります。そのまま放置してもよさそうです。でも、装置Aからの取得指示が装置B届いてないケースもあり得ます。メッセージキューが詰まっていて、送信自体が出来ていないのかもしれません。
過剰設計はなぜうまれる？
ソフトウェア開発の現場では、対抗装置の挙動が不透明だったりすると、極力正常系に落とし込めるような設計にしたがる傾向があります。もちろん必要な設計である場合がほとんどでしょう。ただ、工程が進み対向装置の動作が明確になってくると、準正常系でのケアが不要だったことや、実は規格・機能の目的からい逸脱していることが発覚したりします。準正常系設計時にこそ、規格・機能の目的を把握していることが重要といえます。
過剰設計の弊害
とはいえ、準正常系を手厚くしただけ動作的には問題なさそうです。ただし、判定分、検索処理が多発することによるオーバーヘッドは確実に増加します。競合他社と処理速度を競うような装置の場合は、致命傷になりかねません。また、システムテストの立場では、あらゆるケースでの動作を反映したテストを実行しなければなりません。また、そこで不具合が発見されれば、複雑化した準正常系の処理を修正するために処理がさらに複雑化するかもしれません。対向装置に挙動が不透明ならば、「評価視点」を設計に加味してみるのもいいかもしれません。
何か掘り起こせた？
- 準正常系こそ規格、機能の意図を正確に把握することが必要。
- 評価視点を考慮した設計も必要。
過剰設計はある意味避けきれないのかもしれません。それでも、そのリスクを認識し、できうる限りシンプルな設計を目指したいですね。
おしまい
対向装置の動きが不明なまま設計を進めるなんて状況が回避できればなにも問題ないんですけどね、とか言ってもしかたあるまい。
GoでGoな非同期処理を試してみよう！
非同期処理、皆さんどうコードを書いてますか？
少し前のこと。弊社の若手（？）の方が、『非同期処理めんどくさい！』みたいなことを騒いでいたのですが、そもそも皆さんどうやって非同期処理のソースコードを書いているのだろう？とふと思ったわけです。そもそも『非同期』の定義ってなんだろうという話もでてきそうですが、ぱっと思いつくのは以下のような書き方でしょうか？
- スレッド作成してそこで実行
- async/await を使用して実行
最近の主流は async/await でしょうかね。こちらは多くの言語に実装されています。
ただ私の場合は仕事ではほとんどPythonを書いているのですが、Pythonでのasync/awaitはやや手順が面倒です。他の言語でも似たりよったりでしょうか。
非同期処理が得意なプログラミング言語、それがGo！
ところが、そんなめんどくさい非同期処理を簡単に実現してしまうプログラミング言語が存在するんです。
それは、言わずとしれたGoogle製、Goですね！
場合によっては、『Go言語』とか『GoLang』などとも呼ばれています。検索する場合はそうしないと全然別のものが引っかかってしまいそうですし。。
今回はそのGoを使用して、どのように非同期処理を書いていくかを紹介していきます。
続きを読むRustで設定ファイルを複数読み込む
Rustでの標準的・簡易的な設定ファイルの実装方法と問題点
開発したソフトの実行環境が変わるたびにコーディング・コンパイルをしなおすことのないよう、設定情報をソースコードとは別ファイルにしたり、実行時のOSの環境変数から取得したりする設計は常套手段です。
例えば、Rustの標準クレート「std::env」を使うと、「let var = env::var("TEST").unwrap();」などとするだけで、当プログラムを実行したときに環境変数「TEST」に値が設定されていれば、変数「var」に環境変数「TEST」の設定値が入ります。
また、クレート「dotenv」を使って、実行プログラムと同じディレクトリに「.env」というファイルを作成し、そこに設定情報を記載しておき、読み取るコード側では定数をまとめた構造体を作って解析させる、という方法が用いられていたりします。
ですが、これらの手法では、設定情報が多くなる場合（メッセージやSQLなども設定ファイルにする場合など）に、アプリの保守がしづらくなります。
実行前に大量に環境変数に値を設定するのは現実的ではありませんし、「dotenv」で「from_path」メソッドを使っても、複数のファイルを読み込ませることができないようにみえます。
自由度が高く保守しやすい設定ファイル設計に
そこで、今回は以下のような仕組みを作りましたので、紹介します。
- 実行ファイルと同じディレクトリに、設定ファイル群を保存する「config」ディレクトリを生成しておく。
- 「config」ディレクトリには、設定ファイルを任意のファイル名でいくつ保管してもよい。配下にディレクトリをいくつ生成してもよい。
- 設定ファイルは「toml」形式とし、拡張子も「.toml」とする。（「config」ディレクトリ配下の「.toml」ファイルだけ読み込む）※Rustの依存ライブラリ定義ファイル（cargo.toml）も「toml」形式なので、合わせました。
実装
オリジナル設定ファイル例（config\config.toml）
[csv.output]
file_path = "{CUR}//data//output_%Y%m%d_%H%M%S.csv"
char_code = "shift-jis"
[calc]
value1 = 10
value2 = 20
Rust依存関係設定ファイル（cargo.toml）
[package] name = "config-file-test" version = "0.1.0" [dependencies] lazy_static = "1.4.0" toml = "0.5.6"
Rustソース（main.rs）
以下のように設定値を呼び出します。
#[macro_use] extern crate lazy_static; extern crate toml; mod initialize; use initialize::file_config::CONFIG; fn main() { // 「as_str()」メソッドにて、文字型として呼び出しています。 // 初めて「CONFIG」が参照されるタイミングで「file_config.rs」が実行され、設定ファイルの内容がメモリに展開されます。 let char_code = CONFIG["csv"]["output"]["char_code"].as_str().unwrap(); println!("char_code = {}", char_code); // 標準出力結果「char_code = shift_jis」 // 「as_integer()」メソッドにて、数値型として呼び出しています。 // このタイミングでは、すでにメモリに展開された値を参照しているだけです。 let value1 = CONFIG["calc"]["value1"].as_integer().unwrap(); let value2 = CONFIG["calc"]["value2"].as_integer().unwrap(); println!("value1 + value2 = {}", value1 + value2); // 標準出力結果「value1 + value2 = 30」 }
読み込む設定の定数の型を予め構造体(struct)で定義しておく手段もありますが、定数が増えるごとに構造体も増やしていく作業が面倒なので、上記のような参照方法を紹介しました。 ただ、参照の都度「as_～()」メソッドで型変換するので、処理性能を追求する必要がある場合は、構造体で型を定義しておいたほうがいいかもしれません。
Rustソース（initialize\mod.rs）
本編には関係ないですが、設定ファイルは一度読めばいいので、主処理と切り離しやすいようモジュールにしています。
pub mod file_config;
Rustソース（initialize\file_config.rs）
設定ファイル（.toml）を解析してメモリ上に展開し、上記のように呼び出せるように準備する処理です。 設定ファイルが存在しなければ、新たに生成します。 その場合の初期値は、以下の定数「DEFAULT_CONFIG」に書いています。
use std::io::{BufReader, Read, BufWriter, Write}; use std::fs; use std::fs::{File, DirBuilder}; use std::path::Path; use std::env; use toml::Value; lazy_static! { pub static ref CONFIG:Value = { return load_config(); }; } const DEFAULT_CONFIG: &'static str = r#" [csv.output] file_path = "{CUR}//data//output_%Y%m%d_%H%M%S.csv" char_code = "shift-jis" [calc] value1 = 10 value2 = 20 "#; // toml形式の設定ファイルを読み込む fn load_config() -> Value { // 当プログラムのディレクトリ let cur_path_str = env::current_exe().unwrap().clone(); let cur_path = Path::new(&cur_path_str); let cur_dir = cur_path.parent().unwrap().display(); // 当プログラムのディレクトリ配下に存在する該当拡張子のファイルパスを取得 let file_paths = get_path(Vec::new(), &cur_dir.to_string(), "toml"); // toml形式変換前の設定文字列 let mut conf_toml_str = String::new(); // 全ファイルをテキストで読み込み for path in file_paths.iter() { conf_toml_str = format!("{}{}", conf_toml_str, get_text_file(Path::new(&path), "toml")); } // 設定を1件も取得できていなければ if conf_toml_str.len() < 1 { // 設定ファイルを保存するディレクトリを生成 let path_str = format!("{}//config//config.toml", &cur_dir); let path = Path::new(&path_str); let dir = path.parent().unwrap(); DirBuilder::new().recursive(true).create(&dir).unwrap(); // 設定ファイルのパスを書き込みモードで開く。これは`io::Result<File>`を返す。 let file = match File::create(&path) { Err(e) => panic!("couldn't create {}: {}", path_str, &e.to_string()), Ok(file) => file, }; // バッファリングされたストリーム出力とする let mut f = BufWriter::new(file); // 設定ファイルへ記述 conf_toml_str = DEFAULT_CONFIG.to_string(); match f.write_all(conf_toml_str.as_bytes()) { Err(e) => panic!("couldn't write {}: {}", path_str, &e.to_string()), Ok(_) => println!("{} writes :{}\n", path_str, conf_toml_str), } } // 文字列内に「{CUR}」が存在すれば、当プログラムが存在するディレクトリとみなして、カレントディレクトリに置換 conf_toml_str = conf_toml_str.replace("{CUR}", &format!("{}", &cur_dir)); // 設定をtoml形式に変換して返す conf_toml_str.parse::<Value>().expect(&format!("couldn't parse config file to toml format.{}", &conf_toml_str)) } fn get_path (mut files: Vec<String>, target:&str, path_ext:&'static str) -> Vec<String> { for file_path in fs::read_dir(target).unwrap() { let file_path = file_path.unwrap().path(); if file_path.is_dir() { files = get_path(files, &file_path.display().to_string(), path_ext); } else { match file_path.extension() { _path_ext => files.push(file_path.display().to_string()), } } } files } fn get_text_file (path: &Path, extension: &'static str) -> String { let display = path.display(); match path.extension() { None => return "".to_string(), Some(ext) => { if ext != extension { return "".to_string(); } }, }; // pathを読み込み専用モードで開く let f = match File::open(&path) { Err(e) => panic!("couldn't open {}: {}", display, &e.to_string()), Ok(f) => f, }; // バッファリングされたストリーム入力とする let mut br = BufReader::new(f); // ファイルの中身を文字列に読み込み let mut conf_toml_str = String::new(); match br.read_to_string(&mut conf_toml_str) { Err(e) => panic!("couldn't read {}: {}", display, &e.to_string()), Ok(_) => println!("{} contains:\n{}", display, conf_toml_str), } conf_toml_str }
これで拡張子「.toml」のファイルを「config」フォルダに入れておけば、実行の都度全パラメータを自動で読みこみ、Rust内どのモジュールでも「use initialize::file_config::CONFIG;」だけ記述すれば参照できる状態になります。 もし設定ファイルがない場合でも、自動で「config」フォルダとその中に「config.toml」を生成し、ハードコードした初期値を書き込みます。
「rustc 1.42.0」でコンパイルできることを確認しています。
The Continuing Story of Error Correction Code 2
単一パリティ符号とハミング符号
お約束
これからエラー検出・訂正について考えていく訳ですがエラー検出・訂正をするからには何か入力があって、それをどこかに送るなり保存するなりして、受け取った、あるいは読みだしたら間違えているかもしれないからエラーがあるか検査して、その結果エラーがあれば訂正できるなら訂正するわけです。
このシステムは実際には、線でつながっているシリアル通信かもしれないし、衛星通信かもしれないし、CPUにつながっているメモリかもしれないし、はたまたハードディスクに対する読み書きかもしれません。
ただ、エラー検出・訂正についてのみ考えたいのでこれからは以下のような単純なモデルを考えてみます。
送信語
送信者が送信したいデータのビット列。符号器
送信語に誤り検出・訂正のための加工を施す装置。符号語
符号器により送信語に誤り検出・訂正のための加工を施したビット列。通信路
送信側から受信側へ符号語を送る経路。符号語は通信路を通過する際に誤りが加わる可能性がある。受信語
通信路を通って受信した符号語のビット列。
通信路でエラーが発生していなければ符号語と同一となる。復号器
受信語から送信語と思われるビット列を取り出し受信者に渡す。
シリアル通信をイメージしている感じですが通信路をメモリやハードディスクと考えればコンピューターシステムでしょうし、電波だと考えれば無線システムと考えることができます。
単一パリティ符号
送信語の各ビットの中で1であるビットの数が偶数になるように検査ビットを付加する方法を偶数パリティ、1であるビットの数が奇数になるように検査ビットを付加する方法を奇数パリティといいます。
RS232Cで使用されているのがこの単一パリティ符号ですね。
偶数パリティとか奇数パリティと呼ばれているやつです。
偶数パリティであれば、送信符号の1のビット数を数えた結果が奇数であれば検査ビットとして1、偶数であれば検査ビットとして0を付加するだけです。符号語の1であるビット数は必ず偶数となります。奇数パリティなら符号語の1であるビットが奇数になるように検査ビットが付加されます。
受信側では受信符号の1の数を数えてこれが偶数であれば受信符号は正しいと認識し、1の数が奇数であれば間違えていると認識します。
（厳密に言えば奇数個の誤りは検出できるが偶数個の誤りは検出できない、となるため偶数ビット誤った場合は正しいと認識してしまいます）
単一パリティ符号は送信語のビット数が何ビットでも構わない、という特徴があります。1のビット数を数えるだけなので送信語は何ビットでも構わないんですね。
ただ、間違ってることはわかってもどこのビットが間違えているのかは分かりません。どこのビットが間違えているのか分からないのだから訂正することもできません。（もし、どこのビットが間違えているのか分かるのならそのビットを反転（1だったら0に、0だったら1に）すれば訂正することができます）
まとめると単一パリティ符号は
- 奇数個の誤りを検出できる。
- 送信語のビット数に制約がない。
- 誤りの場所は分からない。
となります。
検査符号の計算方法
単一パリティ符号の検査符号は偶数パリティであれば、
- 送信語の1のビット数が奇数個であれば1。
- 送信語の1のビット数が偶数個であれば0。
でしたが、これを計算で求められるようにしておきましょう。
各ビットの値は0と1しかとりませんから送信語の各ビットを足していき、その合計が偶数か奇数かを判断すればよい訳です。
合計を2進数で考えると最下位のビットが0なら偶数、1なら奇数ですから合計の最下位だけを取り出せば偶数パリティとなります。
最下位ビットしか必要でないのだから最下位ビット以外は捨てて足し算する、ということにすると計算のルールは以下のようになります。
2進数では となりますが最下位ビット以外は捨てる、としたので
となります。他は普通の足し算ですね。
この計算ルールでパリティ符号を計算してみましょう。
例として以下のような送信符号3ビット（、
、
）、検査符号1ビット（
）の単一パリティ符号を考えます。
送信符号3ビット（、
、
）を全部足した値が検査符号となるのですから偶数パリティの検査符号
は
と表すことができます。
また、奇数パリティであれば
となります。
奇数パリティの検査符号は
- 送信語の1のビット数が奇数個であれば0。
- 送信語の1のビット数が偶数個であれば1。
ですから偶数パリティとは逆になります。だから偶数パリティを反転させればよい→1を足せばよい、ということです。
送信符号が何ビットあっても各ビットをひたすら上記足し算ルールで足していった値が検査符号になる、ということですね。
単一パリティ符号からハミング符号へ
単一パリティ符号はどこかに１ビットの誤りがあればそれを検出できるが、その誤りがどのビットなのかはわからない、という符号です。 誤りがどのビットなのかわからないのですから訂正することもできませんね。
そこで、複数のパリティ符号を付加して誤ったビットの位置を特定できるようにしたものがハミング符号となります。誤ったビットがわかるのですからそのビットを反転（0なら1、1なら0）してやれば訂正できたことになります。問題はどうやって誤ったビットの位置を特定するか、です。
以下の7ビットでハミング符号を構成してみます。
でも何故7ビット？8ビットのほうがきりが良いんじゃないの・・・
ハミング符号を8ビットで構成することはできますが、7ビットのハミング符号は符号理論の中ではきりの良いビット数になります。 理由については後々、数学的考察を行った上で考えてみることにします。 とりあえず、ここではそういうもんなんだ、ということにして先に進みます。
で、どうやって誤ったビット位置を特定するの？
1ビットのパリティでは誤ったビット位置を特定することはできませんが、複数のパリティを付加して誤ったビット位置を特定できるようにします。複数のパリティはそれぞれ異なる送信語の複数のビットを担当してもらいます。それぞれのパリティだけでは担当しているビットの何れかに誤りがある、ということしかわかりませんが複数のパリティの結果から誤りのビット位置を特定します。
では、ハミング符号の作り方、はじまりはじまり・・・
を配置する
は
、
、
を担当してもらいます。
、
、
、
の何れかが1ビット誤りを起こすと
が1になります。
| |
|
|
|
|
|
|
|---|---|---|---|---|---|---|
| |
|
|
|
を配置する
は
、
、
を担当してもらいます。
の隣に
、更にその隣に
を配置します。
、
、
、
の何れかが1ビット誤りを起こすと
が1になります。
| |
|
|
|
|
|
|
|---|---|---|---|---|---|---|
| |
|
|
|
を配置する
は
、
、
を担当してもらいます。
の隣に
を配置します。
、
、
、
の何れかが1ビット誤りを起こすと
が1になります。
| |
|
|
|
|
|
|
|---|---|---|---|---|---|---|
| |
|
|
|
完成
まとめるとこうなります。
| |
|
|
|
|
|
|
|---|---|---|---|---|---|---|
| |
|
|
|
|
|
|
4ビットの送信語と3ビットのパリティで合計7ビットの符号語ができました。3ビットのパリティは以下の式により計算できます。
4ビットの送信語の組み合わせに対して生成されるパリティをすべて計算してみましょう。
| |
|
|
|
|
|
|
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
試してみる
送信語が
のときにが誤って1になった以下のような受信語の場合を考えてみます。
復号器で計算するパリティを、
、
とすると
となり、受信語のパリティ
とは異なっていますからどこかに誤りが発生した、ということがわかります。
を確認する
受信語のは0ですが復号器で計算した
は1です。ということは
の担当しているビットに誤りがあった、ということですね。
、
、
の何れかに誤りがあるようで、少なくとも
は誤っていない、とわかります。
を確認する
受信語のは0ですが復号器で計算した
は1です。ということは
の担当しているビットも誤りがあった、ということですね。
の担当は
、
、
ですからこのうちの何れかに誤りがあったということになりますが、
を確認したときに
は誤っていない、とわかっていますから誤りは
、
の何れかとなります。更に
は誤っていない、ということもわかります。
を確認する
受信語のは0ですが復号器で計算した
は1です。ということは
の担当しているビットも誤りがあった、ということになります。
の担当は
、
、
ですからこのうちの何れかに誤りがあったということになりますが、
を確認したときに
は誤っていない、更に
を確認したときに
も誤っていないとわかっていますから誤りは
である、ということがわかりました。
誤ったビット位置を簡単に特定する方法
パリティビットを順番に確認しながら誤ったビット位置を特定してきましたが、実は誤ったビット位置を特定する方法があります。 受信語のパリティは
ですが復号器で計算したパリティは
です。二つのパリティの異なっているビットを1としたビット列を作るとこのケースではすべてのパリティが異なっていますからというビット列が得られます。これを2進数として考えると10進数では7ですね。よって誤りがあったのはビット7である
です。
は
に対応していますから誤りがあったのは
である、となります。
ただ、この方法はこうなるようにパリティ符号を構成したからであってパリティ符号すべてがこういう特徴を持っている訳ではありません。この辺も後々考えていきます。
でも、なんか信じられん・・・
ではもう少し試してみましょう。 送信語が
のときにが誤って受信語が以下のようになった場合、
復号器で計算したパリティは
受信語のパリティは
二つのパリティの異なるビットを1としたビット列はであり10進数で表すと5。誤りはビット5であるから
で
が誤っているよ、ということで検出成功です。
いや、じゃぁパリティが誤ったら？
送信語が
のときにが誤って受信語が以下のようになった場合、
復号器で計算したパリティは
受信語のパリティは
二つのパリティの異なるビットを1としたビット列はであり10進数で表すと4。誤りはビット4であるから
で
が誤っているよ、となります。
2ビット間違えたらだめじゃね？
はい、ここまでの話はあくまで1ビット誤ったらその位置が特定できるよ、ということで2ビット間違えた時は考えていません。2ビット、あるいはそれ以上誤ったらどうなるのでしょうか？誤りが検出できる？訂正は可能？
つっこみどころは色々ありますが、今回の話はここまで。
次回は、ハミング距離を考えてみましょう。
