Mã Gray
Bảng mã Gray 2-bit
00 01 11 10 |
Bảng mã Gray 3-bit
000 001 011 010 110 111 101 100 |
Bảng mã Gray 4-bit
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 |
Mã nhị phân phản xạ, cũng được biết đến với tên gọi là mã Gray – đặt theo tên của Frank Gray, là một hệ thống ký số nhị phân, trong đó hai giá trị liên tiếp chỉ khác nhau một chữ số.
Lúc đầu, mã nhị phân phản xạ được phát minh với mục đích ngăn ngừa tín hiệu ngõ ra không chính xác của các bộ chuyển mạch cơ điện. Ngày nay, mã Gray được sử dụng rộng rãi để sửa lỗi trong những phương tiện liên lạc bằng số, ví dụ như truyền hình kỹ thuật số mặt đất và một vài hệ thống truyền hình cáp.
Tên gọi
sửaTên gốc “mã nhị phân phản xạ” được đưa ra dựa vào một tính chất của bảng mã Gray: các giá trị ở nửa sau của bảng mã có sự đối xứng với các giá trị ở 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ị. 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 của bảng mã, trong mỗi phần tư của bảng mã, v.v.. Cách gọi thông dụng hiện nay -mã Gray - được đặt theo tên của nhà nghiên cứu Frank Gray làm việc ở phòng thí nghiệm Bell. Gray đã dùng mã này trong hệ thống thông tin mã xung của ông, trong một bằng sáng chế xin cấp vào năm 1947 (được cấp vào năm 1953). Thực ra, Gray không phát minh ra mã này, mà trong bằng sáng chế của mình,ông ta chỉ trích dẫn và gọi đó là “mã nhị phân phản xạ”.."[1]
Lịch sử và các ứng dụng thực tiễn
sửaMã nhị phân phản xạ đã được ứng dụng trong những câu đố toán học trước khi trở nên phổ biến trong lĩnh vực kỹ thuật. Kỹ sư người Pháp Émile Baudot đã dùng mã Gray trong hệ thống điện báo vào năm 1878. Ông ta đã được nhận huân chương Bắc đẩu bội tinh cho công trình này. Mã Gray đôi khi bị gán nhầm là được đặt tên theo Elisha Gray, chẳng hạn trong một cuốn sách giáo khoa bàn về điều chế mã xung..[2].
Frank Gray, nhà vật lý thuộc phòng thí nghiệm Bell, người nổi tiếng với việc phát minh ra phương pháp tín hiệu hoá được dùng cho tivi màu tương thích, đã phát minh một phương pháp để chuyển đổi tín hiệu tương tự sang những nhóm mã nhị phân phản xạ bằng cách dùng thiết bị dựa trên đèn chân không..[3]. Phương pháp và các thiết bị này được cấp bằng sáng chế năm 1953 và kể từ đó Gray được lấy tên để đặt cho loại mã này. Loại thiết bị “đèn PCM” mà Gray mô tả trong bằng sáng chế của mình đã được chế tạo thực sự bởi Raymond W. Sears của phòng thí nghiệm Bell, cùng làm việc với Gray và William M. Goodall, là người đã gợi ý cho Gray về việc dùng mã nhị phân phản xạ..[4].
Trong thời kỳ đó, Gray đã hết sức thích thú với việc dùng mã này để tối thiểu hóa sai số trong việc chuyển đổi từ tín hiệu tương tự sang tín hiệu số; và cho đến tận bây giờ, mã mang tên ông vẫn còn được dùng với mục đích này cùng với một số mục đích khác nữa.
.svg)
Trong các thiết bị đo góc quay, người ta thích dùng mã Gray hơn so với mã nhị phân bình thường. Nếu góc quay được biểu diễn bằng mã nhị phân bình thường, khi chuyển từ góc quay này sang góc quay kế tiếp, do có sự thay đổi nhiều bit một lúc trên mã góc quay, có khả năng thiết bị đo đọc nhầm sang mã của một góc quay khác xa với hai góc quay đang xét. Vì tính chất xoay vòng của mã Gray, mã của hai góc quay kế cận chỉ khác nhau một bit nên hiện tượng đọc nhầm sang mã góc quay hoàn toàn khác với hai góc quay này là không thể xảy ra.
Người ta có thể dùng mã nhị phân phản xạ Gray làm phương tiện hướng dẫn giải bài toán Tháp Hà Nội. Có thể tìm thấy một phương pháp chi tiết ở đây Lưu trữ 2004-08-21 tại Wayback Machine. Mã Gray cũng hình thành một chu trình Hamilton trên một siêu lập phương, mà mỗi bit được xem như là một chiều.
Code bằng ngôn ngữ Pascal
sửafunction gray(n:byte):byte; begin gray:= n xor (n shr 1); End;
Xem thêm
sửaGhi chú
sửa- ^ F. Gray. Pulse code communication, March 17 1953 (filed Nov. 1947). Bằng sáng chế Hoa Kỳ số 2,632,058, claims 1-9
- ^ K. W. Cattermole, Principles of Pulse Code Modulation, American Elsevier Publishing Company, Inc., 1969, New York NY, ISBN 0-444-19747-8.
- ^ Knuth, Donald E. "Generating all n-tuples." The Art of Computer Programming, Volume 4A: Enumeration and Backtracking, pre-fascicle 2a, 15 tháng 10 năm 2004. [1] Lưu trữ 2006-12-09 tại Wayback Machine
- ^ W. M. Goodall, "Television by Pulse Code Modulation," Bell Sys. Tech. J., Vol. 30 pp. 33–49, 1951.
Một số hàm và thủ tục về xử lý bit trong pascal
Tham khảo
sửa- Black, Paul E. Gray code. 25 tháng 2 năm 2004. NIST. [2].
- Savage, Carla. "A Survey of Combinatorial Gray Codes." Society of Industrial and Applied Mathematics Review 39 (1997): 605-629. [3][liên kết hỏng].
Liên kết ngoài
sửa- NIST Dictionary of Algorithms and Data Structures: Gray code
- Numerical Recipes in C, section 20.2 Lưu trữ 2008-10-04 tại Wayback Machine Mô tả chi tiết mã Gray (ISBN 0-521-43108-5)
- Hitch Hiker's Guide to Evolutionary Computation, Q21: What are Gray codes, and why are they used? Lưu trữ 2015-10-26 tại Wayback Machine, có mã lập trình C để chuyển đổi giữa số nhị phân và BRGC
- Subsets or Combinations Lưu trữ 2012-02-06 tại Wayback Machine Chỉ cách tạo ra các chuỗi BRGC
- "The Structure of Single-Track Gray Codes" Lưu trữ 2007-03-10 tại Wayback Machine by Moshe Schwartz, Tuvi Etzion
- Single-Track Circuit Codes Lưu trữ 2011-06-07 tại Wayback Machine by Hiltgen, Alain P.; Paterson, Kenneth G.
- Dragos A. Harabor uses Gray codes in a 3D digitizer tại Wayback Machine (lưu trữ ngày 22 tháng 11 năm 2015).
- single-track gray codes, binary chain codes (Lancaster 1994), and linear feedback shift registers are all useful in finding one's absolute position on a single-track rotary encoder (or other position sensor).
- [https://web.archive.org/web/20070930040812/http://etc.manuel-breitfeld.de/gray-code-java-implementierung.html Lưu trữ 2007-09-30 tại Wayback Machine * A Gray code implementation in Java to convert decimals Lưu trữ 2007-09-30 tại Wayback Machine