Giới thiệu Mã Nhị Phân Gray
Phạm Trọng Khiêm. Nguyễn Minh Đăng.
Mã Nh Phân Gray:
ị
ộ
(a
ứ ‡ 1 là m t danh sách c a t ỗ ầ danh sách thì ch có m t thành t ỉ t c ủ ấ ả {0.1}n, sao cho m i l n ta di nh ị ộ ố
ị I. Đ nh nghĩa : Mã nh phân Gray th n ị ầ ử n-1,…,a1,a0) ˛ các ph n t chuy n theo th t ứ ự ể c thay đ i. phân đ ổ ượ
{(0),(1)}.
Ví dụ: V i n=1, danh sách có 2 ph n t ớ V i n=2, danh sách có 4 ph n t ớ ầ ử ầ ử
{(0,0),(0,1),(1,1),(1,0)}
ớ
V i n=3, danh sách có 8 ph n t ầ ử {(0,0,0),(0,0,1),(0,1,1),(0,1,0),(1,1,0),(1,1,1),(1,0,1),(1,0,0)}
ị
ị
R , " n ‡
G ¨ 1G 0;
Mã Nh Phân Gray: II. Công th c xác đ nh mã Gray: ứ n+1= 0G
n
n
n đ
c xây d ng b ng cách thêm 0 vào m i ph n t ầ ử ằ ỗ
G ự n.
R là danh sách ng
n
n.
R đ
G c c a danh sách ượ ủ
n
c xây d ng b ng cách thêm 1 vào m i ph n t ầ ử ằ ỗ
n
G ự R.
R ={(00),(01);(11),(10)}
1
1
¨ 1G
0= 0 ; G v i:ớ 0G ượ c a danh sách ủ G 1G ượ c a danh sách ủ 2 = 0G 1. Ví d :ụ G G
3 = 0G
2
¨
1G R = {(000),(001),(011),(010); 2 (110),(111),(101),(100)}
ị
ớ
n
n
¯
n
¯ ( 2n + 2n-1);
Mã Nh Phân Gray: 2. Ghi chú 1: ỗ ‡ 1 ta có: V i m i n R = G G 2n-1 ; R = 0G 1G n V i:ớ 2n-1 = (10…0)2 ; 2n + 2n-1 = (110…0)2 ;
2, ta c ng nh phân
Ví dụ: v i n = 3, đ có (111) ớ ể
ộ (011)2 ¯ ị (100)2 = (111)2
Mã Nh Phân Gray:
ị
3. Ghi chú 2:
ầ ử ụ ợ ậ
, ví d : M = {1,2,…,n} và t c các t p con c a M. G i vector ủ ậ ọ ủ ấ ả
˛ ợ ư ủ
Xét 1 t p h p M có n ph n t t p h p P(M) c a t ậ đ c tr ng c a T ặ XT = (an-1,…,a1,a0) ˛
T P(M) là XT. Ta đ tặ {0,1}n , sao cho: ai=1 " n-i ˛ T; ai = 0 " n-i ˇ
Ví d : ụ Cho M = {1,2,3}; n = 3
˘
P(M) = {( ),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3)} Xét T = {(1,3)}. Suy ra : XT = ( 101)
ị
Mã Nh Phân Gray: 4. Đ nh nghĩa kho ng cách Hamming d(T,S):
ả ị
P(M), ta đ nh nghĩa kho ng cách Hamming
S| , T D ả (S\T).
ậ ủ
ợ
ỗ ậ ả
ự ỏ
Xét T, S ˛ ị S = (T\S) ¨ d(T,S) = |T D V y mã nh phân Gray chính là 1 danh sách c a P(M) ị sao cho 2 t p h p liên ti p c a danh sách này có ế ủ ậ kho ng cách Hamming b ng 1; nghĩa là m i t p h p ợ ằ con c a M đ c xây d ng b ng cách thêm hay b 1 ượ ủ đi m vào t p h p đ ng tr ợ ứ ậ ằ ướ . c
ể Ví dụ:
Ta có: T và S là 2 t p h p liên ti p ế
T = {(1) } , S = { (1,3) } , R = { (2,3) } ợ T và R là 2 t p h p không liên ti p. ợ ậ ậ ế
Mã Nh Phân Gray:
ị
(3) = (3) = (001) (S\T) = ˘ ¨
Ta xét: T D Ta tính kho ng cách Hamming :
S | = | (001) | = 1
S = (T\S) ¨ ả d(T,S) = | T D ợ ộ ị
(R\T) = (1)¨ R = (T\R) ¨ (2,3) = (1,2,3) = (111)
V y t p h p (T,S) là m t mã nh phân Gray. ậ ậ Ta xét: T D Ta tính kho ng cách Hamming :
ả d(T,R) = | T D 1
V y (T,R) không ph i là m t mã nh phân Gray. ậ R | = | (111) | = „ 3 ả ộ ị
Mã Nh Phân Gray:
ị
:
ị
1. Đ nh lý 1
ị
: Ta đ t:ặ
III. Các đ nh lý
G
n = {gn(0),gn(1),…,gn(2n-1)} 1, 0 £
r < 2n, k = 2n + r, ta có :
v i n ớ
gn+1(r) = 0gn(r) ; gn+1(2n + r) = 1gn(2n-1-r);
‡
Ví d :ụ v i n = 1 ta có: ớ
1 = {g 1(0),g1(1)} = {(0)2,(1)2}
G
Mã Nh Phân Gray:
ị
r < 4;
Ví d (tt)ụ v i n = 2 ta có: ớ G 2 = {g 2(0),g2(1), g2(2), g2(3)} = {(0)2,(1)2 ,(3)2 ,(2)2}; g3(r) = 0g2(r), " 0 £ g3(4) = 1g2(3) = 4 + g2(3) = 6 = ( 110)2 g3(5) = 1g2(2) = 4 + g2(2) = 7 = ( 111)2 g3(6) = 1g2(1) = 4 + g2(1) = 5 = ( 101)2 g3(7) = 1g2(0) = 4 + g2(0) = 4 = ( 100)2
Mã Nh Phân Gray:
ị
1.1 Ghi Chú:
0
£ < r
n 2 ,
= r
...
b b
2
b b ( n 1 n
Với
) ta có: 1 0 2
n
= ¯
- -
2
- = 1
r
...
b b
1
b b ( n 1 n
b b ) , 1 0 2
2
= =
- - -
n
Ví d :ụ với n = 3, r = 2, ta có: r
2 (010) ; 2 - = - = = 1
r
2
= 8 3 5 (101)
(010)
2
2
-
Mã Nh Phân Gray:
ị
2) Đ nh lý 2: ị
(
...
b
j 2 ,
0
b b n n
-1
= b b ) 1 0 2
j
= b n
˛ Gi r s : ả ử = n [0, 2 [ , r (cid:229)
0
£ £
( )
...
a a
j n 1
n n ,
g r n
-= ( a n
) 1 0 2
1
˛ G ‡
ứ ơ ả ủ ị
b
1
j
j
= =
¯ " £ £ -
n 1
a b
j n
b + j a mod 2, 0 i
j
£ <
i n
j
" £ £ - Ta có công th c c b n c a mã nh phân Gray là: 1 mod 2, 0 j (cid:229)
ị
3
2
0
+
=
2
1 0.2 g
+ 1.2 = ( (5)
+ 0.2 a a a ) 2 1 0 2
3
1.2 0
=
(5)
(111)
g
2
= + = } 3
mod 2 1 0 1
và
Mã Nh Phân Gray: •Ví d :ụ V i n = 3, r =5, ta có: ớ r = = r ˛ 3 5 (0101) [0,2 [ , = = = (cid:222) = b b b b 1, 1, 0, 0 1 2 3 = + = = ¯ mod 2 1 0 1 b b 2 3 = + = = ¯ mod 2 0 1 1 b 1 = ¯ b 0
b 2 b 1
=
=
a 2 a 1 a 0 =
mod 2
mod 2 1
a i
a 2
b 2
£ < i
2
=
+
= + =
=
mod 2
mod 2
mod 2 1 1 0
(cid:229)
a 2
a 1
b 1
3 a i
£ < 1 i
3
=
=
+
+
= + + =
mod 2
mod 2
mod 2
mod 2 1 1 1 1
(cid:229)
b 0
a i
a 2
a 1
a 0
£ < i
0
3
(cid:229)
Mã Nh Phân Gray:
ị
m
˝ £
•2.1 Ghi chú 1: r ˛ = r
n [0,2 [ b
j 2 ;
[0,2 [,1 n = "
0, j j £ £ (cid:229) j m
= a = £ £ a
j
2 ; b b , 0 j m 1 0
g r
( )
m j j j +
1 j ¯ " £ £ - (cid:229) j m 1 £ £ - a , 0 j n 1; j a = ậ
a " £ £ - j
0, n j m 1; j " £ £ - =
( )
g r
m g r
( )
n (cid:222) 4 ˝ £ j 2 3 0 4 = = 3
[0,2 [
= [0,2 [,1 3<4;
+ + + + = •Ví d :ụ
r
7 2 2 2 1
2 b 2 2 b
2 b
3 b
0 b
1 j b
4 (00111) ;
2 (cid:229) £ £ j 4
j
b
0,
4 2 0
=
= =
a =
a + + a + Do b
:
3
g
(7) 0, 3
j
2 4;
a
0
2 1
2 2 3
2 ; " £ £ 4 j 0 a
1 2 3 (cid:229) 3 0
+ = + = a = 1 1 0; j
b
1 0 a = + = 1 1 0; = 1 g 2 a = = + = 1 0 1; b
2
+
b
3 2 (7)
g (7) (0100)
=
(100) 3 2 £ £ a = + = 0 0 0; b
0
= +
b
1
b
2
= +
b
3 b
4 3 ‡ ˛ r =
n
[0,2 [, r b 0; j =
j
2 ,
b
n (cid:229) 0
= = £ £ a j
2 ; a j n
b b , 0 j n 1 + j j j j 1 g r
( )
n ¯ " £ £ - (cid:229) j n 1 n b =
b = b
j
2 , 1, 0 0
+ =
r 2 £ £ - j n +
1 n (cid:229) 0 j n n + = a b = £ £ g (2 r ) a
j
2 ; , 0 j n
; + + 1 n j j b
j 1 j ¯ " £ £ (cid:229) 0 j n £ £ j " £ £ - - ¯ " £ £ - j j j j ¯ ¯ ¯ n 1 j
=
+
1
=
n - - - n 1 n - 1
g n
+
n
(2 =
)
r 1
a +
j
2 ( n
+
n
1)2 1
2 + 1 n j n
a
n 1 (cid:222) ¯ (cid:229) - j n +
1 n 0
= £ £ - +
n
(2 2 ) 2
ng r
( ) ¯ = 2,
= = = = 1, 1, 0 b
1 a
0 a
1 n = = = 1, 1 1 2 •Ví d :ụ
=
r
n
2,
=
b b
(
r
)
1 0 2
=
ng r
g
( )
2
+ = =
r
6 (
2
a =
b b b 1 1 0 0 0 1 b
b
0,
0
1
= + =
2 a =
b ¯ ¯ 0) =
3 j a = 2
g b
2
n
(2 =
(10) ,
b
0,
0
2
=
=
a a
3;
)
(
(2)
1 0 2
=
b
b bb
(110) ,
)
2
0 2
2
=
= + =
b
a
0 1 1;
1
1
= + =
b
1 0 1(
do
3
=
+ =
g
r
(6)
) 2 5; ¯ +
1 n 3 j (cid:229) 2 £ £ n = +
n
(2 =
n
1
2 ) (011) 0
j
=
(110) =
(101) 5 g +
(2 r ). + g r
( )
n 2 2 2 n 1 - ¯ ¯0
V y ta có:
=
ị
Mã Nh Phân Gray:
r ˛
} 4
Mã Nh Phân Gray:
ị
• Ghi chú 2:
n
1,
Mã Nh Phân Gray:
ị
b
=
Thì ta đ
c:ượ
-=
b
a
1,
n
n
1
=
a
b
b
b
a
, 0
, 0
j
j
n
n
1;
2;
a
b
=
b
a
=
b
b
1;
1
=
+
a
n
Mã Nh Phân Gray:
ị
Mã Nh Phân Gray:
ị
