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) {}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. | 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) {}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 | 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) {}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 ;
