Хэммингийн хоёртын код

Хэммингийн (7,4) код нь анх үгсийн сангийн 4 бит урттай 2⁴=16 янзаар илэрхийлэгдэх үгийг кодлох дээр зохиогдсон.

Аливаа r > 1 бодит тооны хувьд шугаман код (n,k ) -г n=2r-1 , k=2r-r-1 байхаар үүсгэж болно.
r=3 үед n=2³-1= 8-1=7 , k=2³-3-1=8-3-1 = 4 болж Хэммингийн (7,4) код үүсч байна.

(7,4) Хэммингийн код нь (d1 d2 d3 d4 ) 4 бит урттай үгэн дээр нэмэлт бит (redundancy bit) гэх (p1,p2,p3) битүүдийг нэмж өгдөг.

( Redundancy bit ) - үгийг алдаагүй дамжуулах ,алдааг илрүүлэх боломжийг нэмэгдүүлж өгдөг нэмэлт бит юм.

d1 d2 d3 d4 + p1 p2 p3 => d1 d2 d3 d4 p1 p2 p3
Бодит тоон хоёр утгатай төгсгөлөг талбарыг GF(2) = F₂ = {0; 1} = Z/2 гэж илэрхийлнэ.
F₂ төгсөглөг талбар дээр

p1=d1+d2+d4
p2=d1+d3+d4
p3=d2+d3+d4 гэж илэрхийлж болох d1 d2 d3 d4 оршин байна.

Зурагт үзүүлсэн графикаас харахад p1 нь d1 ,d2 ,d4 өөс хамааралтай болох нь харагдаж байна.
Эндээс p1=d1+d2+d4 гэж илэрхийлж болно.

Хэммингийн кодын (7,4) гэсэн тэмдэглэгээ нь :

(source word) үндсэн мэдээллийн үг нь 4 бит урттай ,
(codeword) кодлогдсон үг нь 7 бит урттай гэдгийг илэрхийлдэг.

Кодлох /Encoding/

0 1 0 0 үгийг Хэммингийн (7,4) кодоор кодлоход

p1=d1+d2+d4 0+1+0=1
p2=d1+d3+d4 0+0+0=0
p3=d2+d3+d4 1+0+0=1 кодлогдсон үг Xcodeword = 0 1 0 0 1 0 1 болж байна.

Үүнийг вектор хэмжигдхүүн хэлбэрээр Xвектор = (0 , 1 , 0 , 0 , 1 ,0 ,1 ) гэж бичиж болно.

Код тайлах /Decoding/

F₂ төгсөглөг талбарт бодит болон комплекс тооны хувьд (x₁ , x₂ , … x_n) (y₁ , y₂ , … y_n) = x₁y₁ + x₂y₂ + … + x_ny_n (1) илэрхийлэл биелэхийг вектор хэмжигдхүүнүүд дээр скаляр үржвэрийг ашиглан тодорхойлж болно.

r , s , t векторуудад

r = (0 ,0 ,0 ,1 ,1 ,1 ,1)
s = (0 ,1 ,1 ,0 ,0 ,1 ,1)
t = (1 ,0 ,1 ,0 ,1 ,0 ,1) гэсэн утга олгоё.

Энэхүү утга олголтын учрыг хүснэгтээр харуулвал:

Битийн байрлал		1	2	3	4	5	6	7
Кодлогдсон үгийн бит		t	s	d1	r	d2	d3	d4
Парити битийн хамрах хүрээ	t	X		X		X		X
	s		X	X			X	X
	r				X	X	X	X

i=0,1,2 ….k гэсэн бодит тоо гэвэл кодлогдсон үгийн 2ⁱ-ээр илэрхийлэгдэх байрлалд Парити бит(Parity bit) байрлана.

Бусад байрлал дээр нь өгөгдөл (data) байрлана.
Парити бит 2ⁱ дэх байрлалаас эхлэн шалгавал 2ⁱ битийг шалгаад 2ⁱ битийг алгасан кодлогдсон үгийн төгсгөл хүртэл шалгана.
Жишээ нь: i=1 гэвэл (2-3 дахь битийг шалгаад 4-5 дахь битийг алгасаад 6-7 дох битийг шалгана ) гэсэн үг.
( Parity bit ) - Парити бит нь тэгшийн бит , шалгагч бит гэсэн хос утгатай.

Хоёртын тэгш хэмт сувгаар Xcodeword = (0 , 1 , 0 , 0 , 1 ,0 ,1 )-ыг дамжуулахад Ycodeword = (1 , 1 , 0 , 0 , 1 ,0 ,1 ) болсон байсан гэж үзвэл

(1) илэрхийллийг ашиглан дараах бодолтыг хийж болно.

y × r =(1 , 1 , 0 , 0 , 1 ,0 ,1 ) × (0 , 0 , 0 , 1 , 1 , 1 , 1)= 1×0 + 1×0 + 0×0 + 0×1 + 1×1 + 0×1 + 1×1= 0
y × s =(1 , 1 , 0 , 0 , 1 ,0 ,1 ) × (0 , 1 , 1 , 0 , 0 , 1 , 1)= 1×0 + 1×1 + 0×1 + 0×0 + 1×0 + 0×1 + 1×1= 0
y × t =(1 , 1 , 0 , 0 , 1 ,0 ,1 ) × (1 , 0 , 1 , 0 , 1 , 0 , 1)= 1×1 + 1×0 + 0×1 + 0×0 + 1×1 + 0×0 + 1×1= 1

0 0 1-г аравтын системд шилжүүлвэл 0 0 1 = 0×2² + 0×2¹ + 1×2⁰ = 1 болно.

Энэ нь хүлээн авсан ycodeword = (1 , 1 , 0 , 0 , 1 ,0 ,1 ) - ын эхний бит нь алдаатай ирсэн гэдгийг харуулж байна.

Хэммингийн (7,4) код нь 4 бит урттай үгийг 7 бит урттай болгон хувиргаж дамжуулах, хүлээж авсан үгийн 1 битийн алдааг засаж чадах аргачлал юм.

Төгсгөлөг талбар дахь (n,k) код түүний матриц

F₂ төгсгөлөг талбар дахь (n,k ) шугаман кодыг мөрүүд нь linearly independent(нэг мөр нь нөгөөгийнхөө дэд олонлог болж чадах ) байх n×k хэмжээст G матрицаар илэрхийлж болно.

G –г үржүүлэгч матриц гэдэг.
F₂ төгсгөлөг талбар дахь (7,4 ) шугаман кодын G -үржүүлэгч матрицын стандарт хэлбэр нь

$\mathbf {G} :={\begin{pmatrix}I_{k}|-A^{T}\\\end{pmatrix}}$ $\mathbf {G} :={\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}_{4,7}$
Харин түүний урвуу матрицыг
$\mathbf {H} :={\begin{pmatrix}A|I_{n-k}\\\end{pmatrix}}$ - шалгагч матриц гэдэг. $\mathbf {H} :={\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\\1&1&1\\1&0&0\\0&1&0\\0&0&1\\\end{pmatrix}}_{7,3}.$
Үржүүлэгч матрицыг ашиглан 1 0 1 1 гэсэн ( мессеж ) өгөгдлийг кодлож үзье.

1 0 1 1 x ${\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}$ = 1 0 1 1 0 1 0

Үржүүлэх үйлдлийг нэг бүрчлэн харуулвал :

    (1 0 1 1) x (1 0 0 0) = 1 x 1 + 0 x 0 + 1 x 0 + 1 x 0 = 1 + 0 +0 + 0 = 1
    (1 0 1 1) x (0 1 0 0) = 1 x 0 + 0 x 1 + 1 x 0 + 1 x 0 = 0 + 0 +0 + 0 = 0
    (1 0 1 1) x (0 0 1 0) = 1 x 0 + 0 x 0 + 1 x 1 + 1 x 0 = 0 + 0 +1 + 0 = 1
    (1 0 1 1) x (0 0 0 1) = 1 x 0 + 0 x 0 + 1 x 0 + 1 x 1 = 0 + 0 +0 + 1 = 1
    (1 0 1 1) x (0 1 1 1) = 1 x 0 + 0 x 1 + 1 x 1 + 1 x 1 = 0 + 0 +1 + 1 = 0
    (1 0 1 1) x (1 0 1 1) = 1 x 1 + 0 x 0 + 1 x 1 + 1 x 1 = 1 + 0 +1 + 1 = 1
    (1 0 1 1) x (1 1 0 1) = 1 x 1 + 0 x 1 + 1 x 0 + 1 x 1 = 1 + 0 +0 + 1 = 0

1 0 1 1 өгөгдөл 1 0 1 1 0 1 0 болон кодлогдсон ба
хүлээн авахад 1 0 1 1 0 1 1 болсон байсан гэвэл код тайлах , алдааг хэрхэн илрүүлж, засахыг үзье.

1 0 1 1 0 1 1 x ${\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\\1&1&1\\1&0&0\\0&1&0\\0&0&1\\\end{pmatrix}}$ = 0 0 1

0 0 1 -ыг аравтын тооллын системрүү шилжүүлвэл 0 0 1 = 0×2² + 0×2¹ + 1×2⁰ = 1 болно. Энэ нь нэг дэх бит дээр 1 0 1 1 0 1 1 алдаатай байна гэдгийг харуулж байна.

Алдаа шалгах ерөнхий алгоритм

0100 гэсэн утга бүхий өгөгдлийг дамжуулаад 0101 утга хүлээн авсан гэвэл аль бит дээр алдаа гарсаныг шалгах алгоритмыг үзүүлье.

Дамжигдаж байгаа өгөгдлийн битийн байрлал нь дараах алгоритмд захирагдана.

Битийн байрлал нь 1-ээс эхэлнэ. бит 1, 2, 3, 4, 5, 6, 7 гэх мэт.
2-ын зэргээр илэрхийлэгдэх байрлал дээр шалгагч бит байрлана.
Бусад байрлал дээр нь өгөгдлийн бит байрлана.
Ямарч өгөгдлийн бит 2 болон түүнээс их шалгагч битийн олонлогт хамаарагдана.

Битийн байрлал		1	2	3	4	5	6	7	шалгагч битийн Утга
Битийн байрлалын харгалзаа		P1	P2	D1	P3	D2	D3	D4
Кодлогдсон өгөгдөл				0		1	0	0
Шалгагч битийн утга		1	0		1
	P1=d1+d2+d4								0+1+0=1
	P2=d1+d3+d4								0+0+0=0
	P3=d2+d3+d4								1+0+0=1

Дараах ерөнхий алгоритмаар аль бит дээр (нэг алдааг шалгах - SEC) алдаа байгааг шалгадаг.
i=0,1,2 ….k гэсэн бодит тоо гэвэл кодлогдсон үгийн 2i-ээр илэрхийлэгдэх байрлалд шалгагч бит байрлана.
Шалгагч бит 2i дэх байрлалаас эхлэн шалгавал 2i битийг шалгаад 2i битийг алгасан кодлогдсон үгийн төгсгөл хүртэл шалгана.

Жишээ нь: i=1 гэвэл (2-3 дахь битийг шалгаад 4-5 дахь битийг алгасаад 6-7 дох битийг шалгана ) гэсэн үг.

Битийн байрлал		1	2	3	4	5	6	7	Хэд дэх бит алдаатайг шалгах
Битийн байрлалын харгалзаа		P1	P2	D1	P3	D2	D3	D4
өгөгдөл		1	0	0	1	1	0	1
Алдааг шалгах хүрээ	ch1	x		x		x		x	1+0+1+1=1
	ch2		x	x			x	x	0+0+0+1=1
	ch3				x	x	x	x	1+1+0+1=1

ch1,ch2,ch4 гэсэн шалгах хүрээнүүдэд харгалзах утгуудад AND үйлдэл хийнэ.
Шалгах хүрээний үр дүн нь “1” байсан бүх хүрээний дугаарыг нэмэхэд хэд дэх бит алдаатай дамжигдсан нь гарна.
Манай жишээний хувьд гурван хүрээний үр дүн гурвуулаа “1” гарсан байна.
Хүрээний дугаарыг нэмэхэд 1+2+4=7 гарч долоо дох бит алдаатай байна гэж үзнэ.

Хэммингийн зай

Хэммингийн зай нь аливаа хоёр ижил урттай (block code) v,u вектор хэмжигдхүүний харгалзах байрлал дээрх ялгаатай элементүүдийн тоогоор илэрхийлэгдэнэ.

v = [ 1 0 1 1 0 1 0 ]
u = [ 0 1 1 1 1 0 0 ]
d(u, v) = 4

хэммингийн зайн чанар :

d(u, v) = d(v, u)
d(u,v) < d(u,w) + d(w,v)

Хэммингийн жин

Хэммингийн жин нь аливаа v,u вектор хэмжигдхүүний “ 0 ”оос ялгаатай элементүүдийн тоогоор илэрхийлэгдэнэ.

v = [ 1 0 1 1 0 1 0 ] => wt(v)=4
u = [ 0 1 1 1 1 0 0 ] => wt(u)=4

хэммингийн зай болон жин нь хоорондоо доорхи хамааралтай.

d(u,v) = wt(u – v)

Хэммингийн жин хамгийн бага байх боломж нь wt() = 2t+1 -р илэрхийлэгдэнэ.

Жишээн дээр авч үзье.
Wt()=3 гэвэл 3=2t+1 болно. t=1 болно
Энэ нь 2 алдааг илрүүлэх эсвэл 1 алдааг засна гэсэн үг.

Илрүүлээд , засах боломжтой хэлбэрийг Wt() = 2t+s+1 гэж тодорхойлж болно.

Энэ нь t+s алдааг илрүүлж t алдааг засна гэсэн үг.
Жишээ нь wt()=5

wt() t s
- 5 =2(0)+4+1 4 алдааг илрүүлээд 0 алдааг засна
- 5 =2(1)+2+1 3 алдааг илрүүлээд 2 алдааг засна
- 5 =2(2)+0+1 2 алдааг илрүүлээд 2 алдааг засна гэж ойлго.

Хэммингийн (7,4,3) код

t -засах боломтой алдааны тоо
t=1 ба s=0 байхад Wt() = 2t+s+1 илэрхийлэл ёсоор Хэммингийн жин хамгийн багадаа Wt()=3 тай тэнцүү байхыг илэрхийлж байна.
Хэммингийн хоёртын(7,4,3)код нь Хэммингийн жин хамгийн багадаа Wt()=3 үед 1 алдааг засахыг илэрхийлнэ.

Код тайлах аргууд

Хамгийн ойр хөршийн (Nearest-neighbor)
Шалгагч матриц (Parity-Check Matrix)
Харилцан олонлог (Coset)
Харилцан олонлог болон шалгах бит синдром (Same Coset-Same Syndrome) гэсэн 4 төрлийн арга байдаг.

Хамгийн ойр хөрш (Nearest-neighbor)-ийн арга.

дамжуулсан үг V=1011011 нь V’=1011001 болж ирсэн гэвэл
1.V’- ийг V- ийн бүх боломжит кодлогдсон үгтэй харьцуулна.
Хэрэв V ’= V байх кодлогдсон үг олдвол дамжуулсан үг алдаагүй ирсэн байна.
2.V ≠ V’ байвал битийн зөрүү нь хамгийн бага байх кодлогдсон үгийг олно.
Жишээ нь :
Бүх боломжит кодлогдсон үгэн доторхи (1011010 ) нь V’=1011001–с ганц битээр зөрж байна. Иймээс хамгийн ойр хөршийн аргаар

дамжуулсан үг нь V=1011011
анхны 4 бит үг нь =1011 гэж олно.

Харилцан олонлог (Coset)-ийн арга.

4 бит урттай 1011 гэсэн өгөгдөл хүлээж авсан гэвэл
1. 4 бит урттай өгөгдлийн бүх боломжит үгийг үүсгэж багануудын эхний мөр болгон авна.
Үүнийг “Haed leader ”гэж нэрлэдэг.
2. Стандарт талбар ( Standart array ) –ын эхний багана болгож хэммингийн жин нь хамгийн бага байх векторуудыг авна.
Үүнийг “Coset leader” гэж нэрлэдэг.
3.Бүх боломжит үгнүүд дээр эхний багана болгож авсан векторуудыг харгалзуулан нэмж стандарт талбарын гишүүдээ үүсгэнэ.

хүлээж авсан үгийг үүсгэсэн стандарт талбар дотор шалгаж 0000001+1011011=1011010 дамжуулсан өгөгдлийг олно.

Харилцан олонлог болон шалгах бит синдром (Same Coset-Same Syndrome)-ын арга

1 0 1 1 0 0 1 x ${\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\\1&1&1\\1&0&0\\0&1&0\\0&0&1\\\end{pmatrix}}$ => uH=010

[1000000]H = 011

[0100000]H = 101

[0010000]H = 110

[0001000]H = 111

[0000100]H = 100

[0000010]H = 010=>vH

[0000001]H = 001…

хүлээж авсан үгийг үржүүлэгч матрицаар үржүүлхэд гарах шалгах бит uH болон
хэммингийн жин нь хамгийн бага байх векторуудыг үржүүлэгч матрицаар үржүүлхэд гарах vH
тэнцүү байна гэсэн теоремоор
uH – vH=0
uH = vH.

010-010=0
0 0 0 0 0 1 0 + 1 0 1 1 0 0 1 = Үндсэн өгөгдөл = 1 0 1 1 0 1 1

Хэммингийн код техникт хэрэгжих жишээ

Гадны холбоосууд