Giới thiệu Mã Nhị Phân Gray
Phạm Trọng Khiêm.
Nguyễn Minh Đăng.
Mã Nh Phân Gray:ị
I. Đ nh nghĩaị:
Mã nh phân Gray th n ị ứ ≥1 là m t danh sách c a t t c ộ ủ ấ ả
các ph n t (aầ ử n-1,…,a1,a0) ∈ {0.1}n, sao cho m i l n ta di ỗ ầ
chuy n theo th t danh sách thì ch có m t thành t nh ể ứ ự ỉ ộ ố ị
phân đ c thay đ i.ượ ổ
Ví dụ:
V i n=1, danh sách có 2 ph n t {(0),(1)}.ớ ầ ử
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)}
Mã Nh Phân Gray:ị
II. Công th c xác đ nh mã Gray:ứ ị
Γ0= 0 ; Γn+1= 0Γn ∪ 1Γn
R , ∀n ≥ 0;
v i:ớ
0Γn đ c xây d ng b ng cách thêm 0 vào m i ph n t ượ ự ằ ỗ ầ ử
c a danh sách ủΓn.
Γn
R là danh sách ng c c a danh sách ượ ủ Γn.
1Γn
R đ c xây d ng b ng cách thêm 1 vào m i ph n t ượ ự ằ ỗ ầ ử
c a danh sách ủΓn
R.
1. Ví d :ụ Γ2 = 0Γ1 ∪ 1Γ1
R ={(00),(01);(11),(10)}
Γ3 = 0Γ2 ∪ 1Γ2
R = {(000),(001),(011),(010);
(110),(111),(101),(100)}
Mã Nh Phân Gray:ị
2. Ghi chú 1:
V i m i nớ ỗ ≥1 ta có:
Γn
R = Γn ⊕ 2n-1 ;
1Γn
R = 0Γn ⊕ ( 2n + 2n-1);
V i:ớ
2n-1 = (10…0)2 ; 2n + 2n-1 = (110…0)2 ;
Ví dụ:
v i n = 3, đ có (111)ớ ể 2, ta c ng nh phânộ ị
(011)2 ⊕ (100)2 = (111)2
Mã Nh Phân Gray:ị
3. Ghi chú 2:
Xét 1 t p h p M có n ph n t , ví d : M = {1,2,…,n} và ậ ợ ầ ử ụ
t p h p P(M) c a t t c các t p con c a M. G i vector ậ ợ ủ ấ ả ậ ủ ọ
đ c tr ng c a T ặ ư ủ ∈ P(M) là XT. Ta đ tặ
XT = (an-1,…,a1,a0) ∈ {0,1}n , sao cho:
ai=1 ∀n-i ∈ T; ai = 0 ∀n-i ∉ T
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)
∅