平成30年春期 問3(ハミング符号)
広告
kaoruさん
(No.1)
解説の下記部分が理解しきれておらず、躓いています。
なぜX1が誤りビットであると判断できるのかが納得できていないのですが、どなたかかみ砕いて説明いただけないでしょうか。
>存在する誤りが1ビットであり、すべての式の結果が0ではないということは、唯一すべての式に含まれているX1が誤りビットであると判断できます。
なぜX1が誤りビットであると判断できるのかが納得できていないのですが、どなたかかみ砕いて説明いただけないでしょうか。
2023.01.13 23:21
wrinklyさん
(No.2)
ハミング符号 1110011(X1X2X3P3X4P2P1)
X1=1,X2=1,X3=1,X4=0,
P1=1,P2=1,P3=0
例えば、
X2が誤り(1--0)だとすると、
X1,X3,X4は正しいのだから、
X1⊕X3⊕X4⊕P1=0
となるはずですが、
1⊕1⊕0⊕1=1
となってしまい矛盾します。(X3,X4も同様)
X1が誤り(1--0)だとすると、
X1⊕X3⊕X4⊕P1=0
0⊕1⊕0⊕1=0
X1⊕X2⊕X4⊕P2=0
0⊕1⊕0⊕1=0
X1⊕X2⊕X3⊕P3=0
0⊕1⊕1⊕0=0
となってすべて整合するので、X1が誤りだとわかります。
以上
X1=1,X2=1,X3=1,X4=0,
P1=1,P2=1,P3=0
例えば、
X2が誤り(1--0)だとすると、
X1,X3,X4は正しいのだから、
X1⊕X3⊕X4⊕P1=0
となるはずですが、
1⊕1⊕0⊕1=1
となってしまい矛盾します。(X3,X4も同様)
X1が誤り(1--0)だとすると、
X1⊕X3⊕X4⊕P1=0
0⊕1⊕0⊕1=0
X1⊕X2⊕X4⊕P2=0
0⊕1⊕0⊕1=0
X1⊕X2⊕X3⊕P3=0
0⊕1⊕1⊕0=0
となってすべて整合するので、X1が誤りだとわかります。
以上
2023.01.14 12:07
boyonboyonさん
★AP シルバーマイスター
(No.3)
文字化けの心配があるので、XORを●で表します。
X1●X3●X4●P1=0
X1●X2●X4●P2=0
X1●X2●X3●P3=0
問題に登場する式は、上記のように表します。
なので、間違えているかどうか、X,Pを取り出し、3つの式に代入して確かめます。
ハミング符号に誤りがなければ、3つの式の値は、0になるはずです。
実際に当てはめて計算すると、
X1,X2,X3,P3,X4,P2,P1
1 1 1 0 0 1 1
X1●X3●X4●P1=1
X1●X2●X4●P2=1
X1●X2●X3●P3=1
となり、ハミング符号に誤りがあることが確認できました。
次は、誤っているビットの特定ですが、1ビットの誤りがあるという条件なので、2つ以上はなしですね。
元の条件にてらし合わせて、
X1が誤りとすると、3つの式の値は上から 1,1,1 3つの式とも逆の値になる ア
X2が誤りとすると、3つの式の値は上から 0,1,1 1つ目は、X2関係なし イ
X3が誤りとすると、3つの式の値は上から 1,0,1 2つ目は、X3関係なし ウ
X4が誤りとすると、3つの式の値は上から 1,1,0 3つ目は、X4関係なし エ
代入の結果は、1,1,1なので X1 が誤りとなります。 ア
X1●X3●X4●P1=0
X1●X2●X4●P2=0
X1●X2●X3●P3=0
問題に登場する式は、上記のように表します。
>ハミング符号 1110011 には1ビットの誤りが存在する。
なので、間違えているかどうか、X,Pを取り出し、3つの式に代入して確かめます。
ハミング符号に誤りがなければ、3つの式の値は、0になるはずです。
実際に当てはめて計算すると、
X1,X2,X3,P3,X4,P2,P1
1 1 1 0 0 1 1
X1●X3●X4●P1=1
X1●X2●X4●P2=1
X1●X2●X3●P3=1
となり、ハミング符号に誤りがあることが確認できました。
次は、誤っているビットの特定ですが、1ビットの誤りがあるという条件なので、2つ以上はなしですね。
元の条件にてらし合わせて、
X1が誤りとすると、3つの式の値は上から 1,1,1 3つの式とも逆の値になる ア
X2が誤りとすると、3つの式の値は上から 0,1,1 1つ目は、X2関係なし イ
X3が誤りとすると、3つの式の値は上から 1,0,1 2つ目は、X3関係なし ウ
X4が誤りとすると、3つの式の値は上から 1,1,0 3つ目は、X4関係なし エ
代入の結果は、1,1,1なので X1 が誤りとなります。 ア
2023.01.14 18:03
kaoruさん
(No.4)
いただいた解説を読んで、自分が入力が3つ以上ある場合のXORの考え方を理解できていなかったことが、躓きの原因であることに気づきました(入力が3つ以上ある場合、1の個数が奇数個であれば1、偶数個であれば0という性質)。
疑問解消いただき、ありがとうございました!!
疑問解消いただき、ありがとうございました!!
2023.01.14 18:39
返信投稿用フォーム
スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。