Mã nhị phân phản xạ, cũng được biết đến với tên gọi là mã Gray. Mã Gray là mã nhị phân mà hai mã liền kề trong bảng mã chỉ khác nhau một bit. Các giá trị ở nửa sau của bảng mã có sự đối xứng với nữa đầu của bảng mã theo thứ tự ngược lại, ngoại trừ bit cao nhất bị đảo giá trị (bit cao nhất là bit ngoài cùng bên trái). Tính chất đối xứng này vẫn đúng cho các bit thấp hơn trong mỗi nửa, mỗi phần tư,... của bảng mã.

Thuật toán sinh bảng mã Gray(n): Với bảng mã Gray(n-1 bits)

1. Gọi L₁ là danh sách cuả mã Gray(n-1 bits), ta tạo được danh sách L₂ bằng cách đảo ngược L₁.

2. Thêm các ký tự '0' vào đầu các phần tử của L₁ và các ký tự '1' vào đầu các phần tử của L_2.

3. Nối L₁ với L₂ ta sẽ có danh sách của bảng mã Gray(n bits).

Ví dụ: muốn tạo một đoạn mã độ dài 3 bits, ta dùng đoạn mã độ dài 2 bits có:

L₁={00,01,11,10} ; L₂={10,11,01,00}

Ta thêm các ký tự '0' vào đầu các phần tử của L₁, tương tự thêm ký tự '1' vào L₂. Ta được:

L₁={000,001,011,010} ; L₂={110,111,101,100}

Nối L₁ với L₂ ta được đoạn mã có độ dài 3 bits như sau

L={000,001,011,010,110,111,101,100}

Yêu cầu: Thể hiện thuật toán trên bằng chương trình nhập vào 1 số nguyên n và xuất ra các phần tử của bảng mã Gray(n bits).

- INPUT: một số nguyên n duy nhất. (1 < n <15)

- OUTPUT: xuất lần lượt các phần tử của bảng mã Gray(n bits). Mỗi phần tử nằm trên 1 hàng.

Giải thích: Với Gray(2) ta xét Gray(1) gồm
1. L₁={0,1} ; L₂={1,0}

2. L₁={00,01} ; L₂={11,10}

3. L={00,01,11,10}