|
|
!ＧＡＩさんの、投稿にありました ハミング・コード についての実験。
! コード自身が、１bit までの誤りビットを、特定する仕組みを、動かしてみます。
! データーが縦に伸びる 列ベクトルは、表示の難があり、行列は、逆にしています。
! プログラムは、冗長ビット４での最大全長１４ビット の場合の例です。
DIM M(1,14), h(14,4), bcc(1,4)
PRINT "--- パリティ 行列 h"
MAT READ h
DATA 0,0,0,1 ! 1 ! 0 は エラー無しの予約値。
DATA 0,0,1,0 ! 2
DATA 0,0,1,1 ! 3
DATA 0,1,0,0 ! 4
DATA 0,1,0,1 ! 5
DATA 0,1,1,0 ! 6
DATA 0,1,1,1 ! 7
DATA 1,0,0,0 ! 8
DATA 1,0,0,1 ! 9
DATA 1,0,1,0 ! 10
DATA 1,0,1,1 ! 11
DATA 1,1,0,0 ! 12
DATA 1,1,0,1 ! 13
DATA 1,1,1,0 ! 14 !オール１の、15 も使用できない。(※注)
MAT PRINT h;
PRINT "上の、14 x 4 の行列 h を、"
PRINT
PRINT "メッセージ・データー 14bit長"
PRINT " （１行 14 列 のベクトル）に乗ずると、"
PRINT " チェック・データー 4bit長"
PRINT " （１行 4 列 のベクトル）が出来る。"
PRINT
MAT READ M ! メッセージ・データー 14bit長
DATA 1,1,0,1,0,0,1,1,0,1, 0,0,0,0 ! 左 10bit長 が、任意で、適当に変えてみるとよい。
! メッセージ・データー 14bit長 を、行ベクトル( m1,m2,m3,,,m14 ) として、
! 行列 h を右に置いて乗ずると、bcc1,bcc2,bcc3,bcc4 …４要素の行ベクトル、
! チェック・データー ができる。この時の積和の計算は、
! １ビット幅の桁上り無し。 排他的論理和 xor や、Modulo2 の和 =MOD( … ,2)
! で行い、４要素は、４bit として求める。これが常に、0000 となる条件が必要です。
!
! そのために、次のような代数式を解く。加算は、桁上り無しの１ビット幅( modulo 2)
!「行列乗算で計算する過程、右(左？)９０度回した状態」
!
!(1) 0= m1 +m3 +m5 +m7 +m9 +m11 +m13
!(2) 0= m2+m3 +m6+m7 +m10+m11 +m14
!(3) 0= m4+m5+m6+m7 +m12+m13+m14
!(4) 0= m8+m9+m10+m11+m12+m13+m14
!
!(3)+(4) 0=m4+m5+m6+m7+m8+m9+m10 +m11 （同じものを加算すると０になる。）
!(1)+(2)+(3) 0=m1+m2+m4+m7+m9+m10 +m12
!(1)+(3)+(4) 0=m1+m3+m4+m6+m8+m10 +m13
!(2)+(3)+(4) 0=m2+m3+m4+m5+m8+m9 +m14
!
! 14 bit の右端 4bit を、下の様に従属させると、左 10bit は、自由に
! 選んでも、上の、0000 となる条件を、満たす事ができる。
LET M(1,11)=MOD( M(1,4)+M(1,5)+M(1,6)+M(1,7)+M(1,8)+M(1,9)+M(1,10) ,2)
LET M(1,12)=MOD( M(1,1)+M(1,2)+M(1,4)+M(1,7)+M(1,9)+M(1,10) ,2)
LET M(1,13)=MOD( M(1,1)+M(1,3)+M(1,4)+M(1,6)+M(1,8)+M(1,10) ,2)
LET M(1,14)=MOD( M(1,2)+M(1,3)+M(1,4)+M(1,5)+M(1,8)+M(1,9) ,2)
!-----エラー・ビットを、順番に置いてみる。０：エラー無しから１～１４まで
FOR j=0 TO 14
CALL error(j)
NEXT j
SUB error(j)
PRINT "-------------------------------------"
PRINT "原形のメッセージ・データー"
MAT PRINT M;
IF j<>0 THEN
LET back=M(1,j)
PRINT "左から";j;"番目のビットが、反転すると"
IF M(1,j)=1 THEN LET M(1,j)=0 ELSE LET M(1,j)=1
ELSE
PRINT "全ビット反転なければ、"
END IF
MAT PRINT M;
!---
CALL check
!---
PRINT "チェック・データーも";bcc(1,1)*8+bcc(1,2)*4+bcc(1,3)*2+bcc(1,4);"になる。２進数"
MAT PRINT bcc;
IF j<>0 THEN LET M(1,j)=back !元へ戻す
END SUB
SUB check
MAT bcc=M*h
FOR i=1 TO 4
LET bcc(1,i)=MOD( bcc(1,i), 2)
NEXT i
END SUB
END
!(※注)
! 書物の、2^(m：冗長ビット) >= (n：データービット)+(m：冗長ビット)+1 の式からは、
! m=4 の場合、n=11 までとなるが、文中の「!オール１の、15」を使用する事に相当し、
! メッセージ・データーの中に m4+m5+m6+m7+m8+m9+m10+m11=0 の条件が発生する。
! (m：冗長ビット)を越えて、制約が入り、11bit が、自由に選べない結果となった。
! 式の等号は、外すべきではないか？
|
|