誤りを見つける工夫(パリティ・チェックディジット・ハッシュ値) 1 / 15

学ぶ > プログラミング > 誤りを見つける工夫(パリティ・チェックディジット・ハッシュ値)

誤りを見つける工夫(パリティ・チェックディジット・ハッシュ値)

領域 (3) プログラミング学習指導要領 (3)ア(ア)・(4)ア(ア)

通信や入力の誤りを見つける仕組み。パリティビット、チェックディジット、ハッシュ値、多数決

誤りは、起こるもの

データを送ったり、保存したり、人が入力したりするとき、0 と 1 が入れかわるなどの誤りが起こることがあります。そこで、誤りを「見つける」ため、または「直す」ための工夫が使われます。

ここが大事見つける(検出(けんしゅつ))と、直す(訂正(ていせい))は、別のこと。

パリティビット

送る側(偶数パリティ)10110010パリティ1 は 4 個(偶数)… パリティビットは 0通信の途中で、ノイズが入る届いた(受ける側)101000101 → 0 に化けた1 は 3 個(奇数)→ 誤りがあると分かる!

上の段は送るデータ 1011001 に、パリティビット 0 を足した 8 ビット。下の段は届いたデータで、4 番目が 1 から 0 に化けている。1 の個数が奇数になるので、誤りが分かる。

送る前に、1 の個数が偶数になるようにビットを足す。届いたあとに数えて、奇数なら、誤りがあったと分かる。

データに 1 ビットを足して、全体の「1」の個数をいつも偶数(ぐうすう)(または奇数(きすう))にする方法です。1 の個数が偶数になるようにする方法を、偶数パリティといいます。

例: 7 ビットのデータ 1011001 には、1 が 4 個(偶数)あるので、足すビットは 0 です。送るのは 10110010 です。

受け取った側は、1 の個数を数えます。偶数なら誤りはないと考え、奇数なら誤りがあったと分かります。

  • 1 ビットだけの誤りは見つけられる。
  • 2 ビットが同時に変わると、1 の個数の偶数・奇数が元にもどってしまうので、見つけられない。偶数個のビットが変わった誤りは見つけられない。
  • どのビットが誤りかは分からないので、直すことはできない。

ここが大事偶数パリティ = 1 の個数を偶数にそろえる。誤りは見つけられるが、直せない。

チェックディジット

商品の番号や会員番号などの最後に、検算用の 1 桁(けた)をつける方法です。入力した人が番号を打ちまちがえたときに、すぐに見つけられます。

例(このサイトでの説明用の方法): すべての桁の和が 10 の倍数になるように、最後の 1 桁を決める。番号 3・7・2 の和は 12 なので、足して 10 の倍数になる 8 をつけて 3728 とする。

1 桁だけを打ちまちがえると、和がずれるので見つけられます。ただし、この方法では隣りあう 2 桁の入れかえ(3728 を 7328 と打つ)は見つけられません。和が変わらないためです。実際の番号(JAN コードなど)では、桁ごとに重みを変えています。隣りあう桁の入れかえの多くも、見つけられるようにしています。

ここが大事チェックディジットは、入力まちがいを見つけるための検算用の桁。

ハッシュ値と、多数決

ハッシュ関数は、データから決まった長さの値(ハッシュ値。メッセージダイジェストともいう)を作ります。同じデータからは、いつも同じ値ができます。データが 1 文字でも変わると、まったくちがう値になります。値からもとのデータを計算で求めることは、現実にはきわめて難しくなっています。

ダウンロードしたファイルのハッシュ値を、公開されている値と比べます。同じなら、ファイルが壊れたり書きかえられたりしていないと確かめられます。

また、同じデータを 3 回送って、多数決(たすうけつ)で正しいものを決める方法なら、誤りを直せます。ただし、送るデータの量が 3 倍になります。

ここが大事ハッシュ値が同じなら、同じデータと考えてよい。1 文字ちがうと、別の値になる。

確認問題

答えを選ぶと、すぐに答え合わせと解説が出ます。すべて正解にすると、学んだしるしがつきます。 正解: 0 / 8

答えを選ぶと、派手な演出が出るよ!

演出ラボで、ほかの演出も、ためせます。

  1. 偶数(ぐうすう)パリティで、4 ビットのデータ 1101 にパリティビットを足す。足すビットは、いくつか。

  2. 偶数(ぐうすう)パリティで、7 ビットのデータとパリティビットを合わせた 8 ビット「10110101」を受け取った。この受け取ったデータについて、正しいものはどれか。

  3. パリティビットで見つけられない可能性があるのは、どれか。

  4. チェックディジットの方法で、すべての桁(けた)の和が 10 の倍数になるように最後の 1 桁を決めます。この方法で、番号 5・9・1 につける 1 桁はいくつか。

  5. チェックディジットのおもな目的はどれか。

  6. ハッシュ値の性質として、正しいものはどれか。

  7. ダウンロードしたファイルのハッシュ値を計算したところ、配布元が公開している値と一致した。この結果から言えることはどれか。

  8. 同じデータを 3 回送り、受け取った側が多数決(たすうけつ)で正しいものを決める方法について、正しいものはどれか。

確認問題の正解: 0 / 8

つぎは