ハミング符号の誤り検出ビットについて

質問

ソフトウエア開発技術者試験のための勉強をしています。
ハミング符号では、例えば情報ビット４ビットには誤り検出ビット３ビットが必要で、この３ビットは情報ビット４ビットのどこに入れても良いとあります。この方式の前提は、あらかじめ送信側と受信側で誤り検出ビットの位置を決めてあるからですよね？つまり受信側が、受け取ったビット列のどこが誤り検出ビットなのかを知らなければ誤りの検出や訂正は出来ない、と理解しています。
よって、「ハミング符号によるチェック方式において”1001101”というビット列を受け取ったが、正しくない。どのビットが誤っているかを示しなさい。」という問題（翔泳社ソフトウエア開発技術者2005年度版P85）は、どこが誤り検出ビットなのか書いていないので解けないと思うのですが、違うでしょうか？

回答No.2

ymmasayan · ベストアンサー

>　ハミング符号では、・・・この３ビットは情報ビット４ビットのどこに入れても
>　良いとあります。
>　この方式の前提は、あらかじめ送信側と受信側で誤り検出ビットの位置を
>　決めてあるからですよね？
その通りです。

>　つまり受信側が、受け取ったビット列のどこが誤り検出ビットなのかを知らなければ
>　誤りの検出や訂正は出来ない、と理解しています。
それで正しいです。
その上、さらにビット間の演算式(チェック式)も知っている必要が有ります。

>　「ハミング符号によるチェック方式において”1001101”というビット列を
>　受け取ったが、正しくない。どのビットが誤っているかを示しなさい。」
>　という問題（・・・）は、どこが誤り検出ビットなのか書いていないので解けない・・・。
その通り解けません。

あくまでもビット配列と演算式が規定されていないと解く事は出来ません。
ビット配列については質問者さんの言われるように、単なる約束事ですから
送信者と受信者が一致していればどのように決めてもいいのです。
事実、書物によってビット配列は色々です。

蛇足ですが、誤りビット１ビットを簡単に見つけられるビット配列をご紹介します。
これを理解するとハミング符号が身近になります。

X1　X2　X3　P3　X4　P2　P1
Xが情報ビット、Ｐが検査ビットです。ビットに前から順に７から１の番号を打ちます。
判定式は
X1＋X3＋X4＋P1＝0
X1＋X2＋X4＋P2＝0
X1＋X2＋X3＋P3＝0
です。
ここで、例えばX3ビットが間違うと１行目と３行目の式がエラーになります。
つまりP1とP3に関する式ですね。
ビット番号に着目して見ましょう。
X3は５番目、P1は１番目、P3は４番目で、１＋４＝５でX3が誤りと言うことを示しています。
他のビットでも試して見てください。

お礼

明快な回答ありがとうございます。
なるほど、教えていただいたビット配列を使うと間違っているビットがどこなのか簡単にわかりますね。とても便利です。

ところで、細かい点なのですが確認させてください。
>　ビット間の演算式(チェック式)も知っている必要が有ります。

これは厳密には、演算式そのものは知らなくても最低限偶数パリティか奇数パリティかさえわかっていればよいのでしょうか？
受信側では誤り検出ビットを１つずつ判定式に含め、各情報ビットを必ず２回以上判定式に使う、という条件さえ満たして任意の判定式を作れば判定できてしまうような気がするのですが。
例えば上記例でいうと、判定式は以下のいずれでも誤りの判定は出来るのではないかと考えました。（もちろんこれらのパターンでは教えていただいた簡単な間違いビットの計算方法は使えなくなりますが）

A）X1を3つにするパターン
X1＋X3＋X4＋P1＝0
X1＋X2＋X4＋P2＝0
X1＋X2＋X3＋P3＝0

B）X2を3つにするパターン
X2＋X3＋X4＋P1＝0
X1＋X2＋X4＋P2＝0
X1＋X2＋X3＋P3＝0

C）X3を3つにするパターン
X1＋X3＋X4＋P1＝0
X2＋X3＋X4＋P2＝0
X1＋X2＋X3＋P3＝0

D）X4を3つにするパターン
X1＋X3＋X4＋P1＝0
X1＋X2＋X4＋P2＝0
X2＋X3＋X4＋P3＝0

回答No.3

ymmasayan

No.2です。追加質問にお答えします。

>　厳密には、演算式そのものは知らなくても最低限偶数パリティか奇数パリティかさえ
>　わかっていればよいのでしょうか？
それではだめでしょうね。
演算式というのは質問者さんの言われるＡ，Ｂ，Ｃ，Ｄ各パターンの内のどれか
(あるいは別のもの)ということです。
これが分らないと、仮に誤り検出は出来たとしても、誤り訂正は出来ません。
ハミング符号は１ビットの誤りは訂正でき、２ビットまでの誤りは検出できる仕様です。

例で説明します。
Ａパターンで１０１０を変換するとP1P2P3が０１０となります。
これが１１１００１０と誤って受信されたとするとＡパターンではP2P3の誤りを検出し、
ＤパターンではP2だけの誤りを検出します。
従ってあらかじめＡパターンである事を知っておかないと誤りビットの特定が出来ない、
つまり訂正が出来ないという事になります。

お礼

なるほど、やってみると確かにそうですね。
すっきりしました。
どうもありがとうございました。

回答No.1

noname#10575

通常、「４ビットの情報ビット」＋「３ビットのチェックビット」を付加して、「符号全体長は７ビット」としていると思います。

正確な問題文が手元に無いので何とも言えませんが、
その問題は、「情報処理技術者試験の過去問」でしょうか？それとも、「翔泳社作成の練習問題」でしょうか？

後者の場合問題そのものに間違いがある可能性も否定できないと思います。

過去問の一例を参考ＵＲＬとしてリンクします。
「ソフトウエア開発技術者」⇒「平成１５年」⇒「問６６」を選択して下さい。

参考URL：

http://smickey.cool.ne.jp/cgi-bin/text/textprint.cgi?c=1&y=15&s=0&no=66

お礼

早速の回答ありがとうございます。教えていただいたサイトの問題ならば納得がいきます。
この問題は翔泳社作成の練習問題だと思います。
問題文はこれで全てで、補足の絵や図などはありません。
この問題の正誤も気になるのですが、理論的に、送信側が適当に（勝手に）誤り検出ビットを情報ビットに混ぜて送って、それで誤りの検出や訂正が出来るものなのかを知りたいと思っています。
受信側で何か数学的な処理を施せば誤り検出ビットがどれかわかるとか。
ネットで符号理論の講義資料などをいろいろ調べましたが、ハミング符号の作り方などは書いてあってもこの点が書いてあるものが見つけられませんでした。