Giới thiệu Mã Nhị Phân Gray

Chia sẻ: Nguyen Thethoi | Ngày: | Loại File: PPT | Số trang:18

Thêm vào BST

Báo xấu

330
lượt xem 53
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mã nhị phân Gray thứ n 1 là một danh sách của tất cả các phần tử (an-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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giới thiệu Mã Nhị Phân Gray

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ử (an-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ΓnR , ∀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. ΓnR là danh sách ngược của danh sách Γn. 1ΓnR được xây dựng bằng cách thêm 1 vào mỗi phần tử của danh sách ΓnR. 1. Ví dụ: Γ2 = 0Γ1 ∪ 1Γ1R ={(00),(01);(11),(10)} Γ3 = 0Γ2 ∪ 1Γ2R = {(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ó: ΓnR = Γn ⊕ 2n-1 ; 1ΓnR = 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)
Mã Nhị Phân Gray: 4. Định nghĩa khoảng cách Hamming d(T,S): Xét T, S ∈ P(M), ta định nghĩa khoảng cách Hamming d(T,S) = |T ∆ S| , T ∆ S = (T\S) ∪ (S\T). 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ụ: T = {(1) } , S = { (1,3) } , R = { (2,3) } Ta có: T và S là 2 tập hợp liên tiếp T và R là 2 tập hợp không liên tiếp.
Mã Nhị Phân Gray: Ta xét: T ∆ S = (T\S) ∪ (S\T) = ∅ ∪ (3) = (3) = (001) Ta tính khoảng cách Hamming : d(T,S) = | T ∆ S | = | (001) | = 1 Vậy tập hợp (T,S) là một mã nhị phân Gray. Ta xét: T ∆ R = (T\R) ∪ (R\T) = (1)∪ (2,3) = (1,2,3) = (111) Ta tính khoảng cách Hamming : d(T,R) = | T ∆ R | = | (111) | = 3 ≠ 1 Vậy (T,R) không phải là một mã nhị phân Gray.
Mã Nhị Phân Gray: III. Các định lý: 1. Định lý 1: Ta đặt: Γn = {gn(0),gn(1),…,gn(2n-1)} với n ≥ 1, 0 ≤ r < 2n, k = 2n + r, ta có : 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}
Mã Nhị Phân Gray: Ví dụ (tt) với n = 2 ta có: Γ2 = {g 2(0),g2(1), g2(2), g2(3)} = {(0)2,(1)2 ,(3)2 ,(2)2}; g3(r) = 0g2(r), ∀0 ≤ r < 4; 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ú: Với 0 ≤ r < 2 , r = (bn −1bn −2 ...b1b0 ) 2ta có: n 2 −1 − r = (bn −1 bn −2 ...b1 b0 ) 2 , b = b ⊕1 n Ví dụ: với n = 3, r = 2, ta có: r = 2 = (010) 2 ; 2 − 1 − r = 8 − 3 = 5 = (101) 2 = (010) 2 n
Mã Nhị Phân Gray: 2) Định lý 2: Giả sử : n ∑ r ∈[0, 2 [ , r = (bnbn -1...b1b0 ) 2 = b j 2 j , bn = 0 0 ≤ j ≤n g n ( r ) = ( an −1...a1a0 ) 2 ∈Γ , n ≥1 n Ta có công thức cơ bản của mã nhị phân Gray là: a j = b j ⊕ b j +1 mod 2, ∀0 ≤ j ≤ n − 1 ∑ a mod 2, ∀0 ≤ j ≤ n − 1 bj = i j ≤i < n
Mã Nhị Phân Gray: •Ví dụ: Với n = 3, r =5, ta có: r ∈[0,2 [ , r = 5 = (0101) 2 = 1.2 + 0.2 + 1.2 + 0.2 0 1 2 3 3 ⇒ b0 = 1, b1 = 0, b2 = 1, b3 = 0 và g3 (5) = (a2 a1a0 ) 2 } a2 = b2 ⊕ b3 mod 2 = 1 + 0 = 1 g3 (5) = (111) 2 a1 = b1 ⊕ b2 mod 2 = 0 + 1 = 1 a0 = b0 ⊕ b1 mod 2 = 1 + 0 = 1 ∑ a mod 2 = a b2 = mod 2 = 1 i 2 2≤ i < 3 ∑ a mod 2 = a b1 = mod 2 + a1 mod 2 = 1 + 1 = 0 i 2 1≤ i < 3 ∑ a mod 2 = a b0 = mod 2 + a1 mod 2 + a0 mod 2 = 1 + 1 + 1 = 1 i 2 0≤ i < 3
Mã Nhị Phân Gray: •2.1 Ghi chú 1: r ∈[0,2 [ ⊆ [0,2 [,1 ≤ n
Mã Nhị Phân Gray: r ∈ [0,23[ ⊆ [0,24 [,1 ≤ 3
Mã Nhị Phân Gray: • Ghi chú 2: ∑ b 2 ,b n ≥ 1, r ∈ [0,2 [, r = = 0; n j j n 0≤ j ≤ n ∑ g n (r ) = a j 2 ; a j = b j ⊕ b j +1 , ∀ 0 ≤ j ≤ n − 1 j 0≤ j ≤ n − 1 ∑β 2 , β n = 1, β n +1 = 0 2 +r = n j j 0≤ j ≤ n ∑α 2 ; α j = β j ⊕ β j +1 , ∀ 0 ≤ j ≤ n; g n +1 (2 + r ) = n j j 0≤ j ≤ n
Mã Nhị Phân Gray: Thì ta được: an −1 = bn −1 , β j = b j , ∀ 0 ≤ j ≤ n − 1; α j = b j ⊕ b j +1 = a j , ∀0 ≤ j ≤ n − 2; α n−1 = β n −1 ⊕ β n = an −1 ⊕ 1;α n = β n ⊕ β n +1 = 1 ∑ n −1 ⇒ g n +1 (2 + r ) = a j 2 + (an −1 ⊕ 1)2 + 2 n j n 0≤ j ≤ n − 2 n +1 = g n (r ) ⊕ (2 + 2 n )
Mã Nhị Phân Gray: •Ví dụ: n = 2, r = 2, r = (b1b0 ) 2 = (10) 2 , b0 = 0, b1 = 1, a0 = 1, a1 = 0 g n (r ) = g 2 (2) = (a1a0 ) 2 = 3; 2 + r = 6 = ( β 2 β1β 0 ) 2 = (110) 2 , β 0 = 0, β1 = 1, β 2 = 1 n α 0 = β 0 ⊕ β1 = 0 + 1 = 1; α1 = β1 ⊕ β 2 = 1 + 1 = 0 α 2 = β 2 ⊕ β3 = 1 + 0 = 1(doβ3 = 0) g n +1 (2n + r ) = g 3 (6) = ∑ α j 2 j = 5; 0 ≤ j ≤2 g n (r ) ⊕ (2n + 2n −1 ) = (011) 2 ⊕ (110) 2 = (101) 2 = 5 = g n + 1 (2n + r ).
Mã Nhị Phân Gray: