| データチェック |
|---|
|
◆ ハミング符号 １ビットの誤りであれば、検出と訂正ができ、２ビットの誤りがあれば検出のみできる。 誤り訂正用符号の１つであり、元のデータに検査用のデータとして付加しているものです。 どこで使用されているかと言いますと、RAID-2 や ECCメモリ などに使用されていますが、どちらもあまり使用されていない技術かもしれません。 出題傾向は、ハミング符号の意味を問う場合と、誤りを訂正したハミング符号はどれかという問題が出るようです。 意味を問われた場合は、「検出と訂正ができる」がキーワードとなりそうです。 下に過去問題を記述します。 X1、X2、X3、X4 の４ビットからなるデータに３ビットの冗長ビット P3、P2、P1 を付加したハミング符号 X1 X2 X3 X4 P3 P2 P1 を考える。 （P3〜P1と順番逆になっているのを気をつけて） 付加ビット P1、P2、P3 は、それぞれ X1 xor X3 xor X4 xor P1 ＝ 0 X1 xor X2 xor X4 xor P2 ＝ 0 X1 xor X2 xor X3 xor P3 ＝ 0 （xor は排他的論理和） となるように決める。 ハミング符号 1110011 には１ビットの誤りが存在します。誤りを訂正した正しいハミング符号はどれか？ (ｱ)0110011、(ｲ)1010011、(ｳ)1100011、(ｴ)1110111 同じ問題が何回か出てきているようです。
まず、誤りのあるハミング符号 1110011を上の式に当てはめると全て結果が 1 になっています。 （本当なら全部 0 ならないといけない） P1、P2、P3の部分はチェック用なので、ここに誤りはないので (ｴ) は違うと思います。 X1、X2、X3、X4 の部分を注目すると、X1 だけが全ての式に出ています。 つまり X2、X3、X4 の１つを反転させても、上の３つ式の結果が全て 0 になる事は無いのではないかと予想できます。 というわけで X1 を反転させてみます。
といいわけで X1 が誤りであるという事になります。よって答えが X1 が反転した (ｱ) という事になります。 ◆ パリティチェック （奇数パリティ、偶数パリティ） コンピュータのデータは2進数のビット列で表してます。 その中の 0 または 1 の個数を調べ、その個数が奇数か偶数なのかをチェックして、データの後ろに添付するというチェックの仕方です。 誤りを検出できますけど訂正はできません。 主にコンピュータ同士の通信（たぶん TCP/IP での物理層）のチェックや、内部の回路でのデータ転送のチェック方式として幅広く使用されています。 奇数、偶数が合わなければ、誤りありとみなされ、データを再送を要求する仕組みだそうです。 ちなみに、このチェックは垂直パリティとも呼ばれます。 特徴としては、高速で１ビットの誤りを検出できますが、訂正とかはできません。 過去問題も意味を問う事が多いみたいです。 ◆ 水平パリティ データを一定のブロック単位またはキャラクタ単位（半角英数）に分けて BCC と呼ばれるパリティビット列を付加して、誤りを検出します。 イメージ的には下の様な感じです。
縦に見て縦に見て偶数パリティの符号をつけます。緑の部分が BCC と呼ばれる符号です。 各列に奇数パリティの符号を付けるかどうかが、ちょっとはっきり分かりませんでした。（水色の部分） 垂直パリティと水平パリティは、併用する事で、１ビットの検出だけではなく訂正もできるようになります。 ◆ チェックサム（または CRC ） チェックサムと言っても色々あるようなのです。 代表的なのものでCRC方式（巡回冗長符号）やMD5方式のチェックサムが存在するようですが、 過去問題として出てきたのはCRC方式（巡回冗長符号）のようです。 （またはただのチェックサムという単語のみで出てたりします。） チェックサムとは、データ転送時に元のデータと、その元のデータを１つずつ足していった合計値をチェック用として添付して送る、誤り検出符号の１種です。 といっても何の合計値か良く分からないので、考え方として例えば「ABC」という文字があります。 これを16進コード文字列に変換した場合、「41 42 43」となります。 チェックサムとは、この合計値の事を言います。（つまり16進数の合計値 C6 がチェック用の値となります。） これが、チェック用の符号として添付されます。 しかし、計算結果が同じになるエラーが発生した場合や、文字の順番が入れ替わる場合などにはエラーチェックができません。 CRCは、上記の欠点を補うように足し算ではなく、割り算で計算されるようです。LHA（ファイル圧縮・解凍ツール）などで使用されています。 |
| TOPページに戻る |