Chào các bạn, hôm nay chúng ta sẽ cùng mổ xẻ một khái niệm cực kỳ thú vị trong khoa học máy tính: Gray Code .

Nếu bạn từng thắc mắc tại sao các kỹ sư phần cứng lại sợ số nhị phân truyền thống (Binary) đến thế, hay tại sao cái volume vặn trên dàn âm thanh lại mượt mà như vậy, thì câu trả lời nằm ở Gray Code.

---

1. Vấn đề của Hệ Nhị Phân (Binary)

Hãy tưởng tượng bạn đang đếm số từ 7 lên 8.

Trong hệ thập phân, nó rất đơn giản: 7 -> 8 .
Nhưng trong hệ nhị phân 4-bit, điều gì sẽ xảy ra?

• 7 là 0111
• 8 là 1000

Bạn thấy đó, để chuyển từ 7 sang 8, cả 4 bit đều phải thay đổi cùng một lúc (3 bit 1 thành 0 , và bit 0 đầu tiên thành 1 ).

Tai hại ở đâu?
Trong thế giới điện tử thực tế, không có gì là “đồng thời” tuyệt đối cả. Có thể bit này đổi nhanh hơn bit kia một chút xíu (nano giây).
Trong khoảnh khắc chuyển giao hỗn loạn đó, hệ thống có thể đọc nhầm thành 1111 (15) hay 0000 (0) thay vì 1000 (8).
-> Đây gọi là Glitch . Trong điều khiển máy móc, glitch này có thể gây ra sai số chết người.

---

2. Giải pháp Gray Code: Mỗi bước chỉ đổi 1 bit

Frank Gray (nhà nghiên cứu của Bell Labs) đã nghĩ ra một cách sắp xếp lại các chuỗi nhị phân sao cho: Hai số liên tiếp nhau chỉ khác nhau đúng 1 bit duy nhất.

Ví dụ so sánh đếm từ 0 đến 3:

Số

Binary

Gray Code

Thay đổi (Gray)

0

00

00

Xuất phát

1

01

01

Đổi bit cuối

2

10

11

Đổi bit đầu

3

11

10

Đổi bit cuối

Bạn thấy sự khác biệt chứ? Ở cột Gray Code, mỗi lần xuống dòng, chỉ có đúng một con số 1 hoặc 0 nhảy mà thôi. Sự “bình yên” này giúp loại bỏ hoàn toàn lỗi Glitch phần cứng.

---

3. Bí kíp tạo Gray Code (Phương pháp Soi Gương)

Làm sao để tạo ra chuỗi này? Có một mẹo cực hay gọi là “Đệ quy phản chiếu” (Recursive Reflection).

Giả sử bạn đã có chuỗi Gray 1-bit: 0 , 1 .
Để tạo chuỗi 2-bit:

1. Soi gương : Lấy chuỗi cũ, lật ngược lại.
   • Cũ: 0 , 1
   • Gương: 1 , 0
2. Dán tiền tố :
   • Chuỗi cũ thêm 0 đằng trước -> 00 , 01
   • Chuỗi gương thêm 1 đằng trước -> 11 , 10
3. Gộp lại : Ta được 00, 01, 11, 10 .

Cứ thế làm tiếp cho 3-bit, 4-bit… Giống như gấp giấy vậy!

---

4. Công thức thần thánh cho Lập trình viên

Nếu bạn là coder và muốn chuyển đổi số tự nhiên n sang Gray code thứ n , đừng dùng đệ quy, hãy dùng Bitwise thần chưởng:

int gray = n ^ (n >> 1); 

Tại sao nó hoạt động?
Công thức n XOR (n dịch phải 1) nghe có vẻ vô lý nhưng lại cực kỳ thuyết phục. Nó tự động tạo ra sự lệch pha 1 bit cần thiết.

Thử với n=3 ( 011 binary):

• n >> 1 = 001
• 011 XOR 001 = 010 (Đây chính là Gray Code của 3!)

---

Visualization

public List grayCode(int n) { 
  List result = new ArrayList<>(); 
  int limit = 1 << n; // 2^n 
  for (int i = 0; i < limit; i++) { 
    int grayReq = i ^ (i >> 1);
    result.add(grayReq);
  }
  return result;
} 

---

5. Ứng dụng thực tế

• Bộ mã hóa vị trí (Rotary Encoders) : Trong các motor, volume xe hơi, robot. Dùng Gray code đĩa quay để biết chính xác góc quay mà không sợ sai số khi quay nhanh.
• Sửa lỗi đường truyền : Trong truyền tín hiệu tivi cáp (QAM), người ta dùng mapping kiểu Gray code để giảm thiểu lỗi bit khi nhiễu.
• Giải thuật di truyền (Genetic Algorithms) : Khi lai ghép các gen (bit string), dùng Gray code giúp các đột biến nhỏ không làm thay đổi giá trị số quá lớn đột ngột.

Kết luận

Gray Code là minh chứng cho việc thay đổi ít nhất có thể lại mang lại sự ổn định cao nhất.

Lần tới khi bạn thấy một thanh trượt volume hoạt động mượt mà, hãy thầm cảm ơn GrayCode nhé!