Bit chẵn lẻ

Bách khoa toàn thư mở Wikipedia
8 bit dữ liệu byte có bit chẵn lẻ
Quy luật số chẵn Quy luật số lẻ
00000000 000000000 000000001
10100001 101000011 101000010
11010001 110100010 110100011
11111111 111111110 111111111

Bit chẵn lẻ (tiếng Anh: parity bit), hoặc bit kiểm tra (tiếng Anh: check bit), là một bit được thêm vào một chuỗi mã nhị phân, để kiểm tra phát hiện lỗi trong dữ liệu khi truyền đưa hoặc đọc/ghi trên phương tiện lưu trữ. Nó là dạng mã phát hiện lỗi đơn giản nhất. Các bit chẵn lẻ thường được áp dụng cho các đơn vị nhỏ nhất của giao thức truyền thông, phổ biến nhất hiện nay là các octet (byte) 8 bit, mặc dù về nguyên tắc chúng áp dụng tổng quát cho tất cả các dạng chuỗi có số bit khác.[1]

Với chuỗi octet thì khung truyền đưa chuỗi có 9 bit, trong đó có 8 bit dữ liệu và bit thứ 9 là bit chẵn lẻ. Nội dung bit chẵn lẻ có giá trị bằng số bù nhị phân cho tổng các bit của octet để tổ hợp octet + parity luôn luôn hoặc là một số chẵn hoặc là một số lẻ, tùy theo lựa chọn của nhà thiết kế hệ thống truyền đưa.

  1. Bit chẵn lẻ dùng quy tắc số chẵn (even parity bit), thì bit chẵn lẻ có giá trị bằng 1(2) khi số lượng các bit 1 trong octet là một số lẻ. Khi cộng thêm bit chẵn lẻ vào, tổng số lượng bit có giá trị bằng 1(2) là một số chẵn.
  2. Bit chẵn lẻ dùng quy tắc số lẻ (odd parity bit). thì bit chẵn lẻ có giá trị bằng 1(2) nếu số lượng các bit 1 trong octet là một số chẵn. Khi cộng thêm bit chẵn lẻ vào, tổng số bit có giá trị bằng 1(2) là một số lẻ.

Bit chẵn lẻ dùng quy tắc chẵn là một trường hợp đặc biệt của kỹ thuật kiểm tra độ dư tuần hoàn (CRC - cyclic redundancy check). Trong CRC, bit CRC được kiến tạo bằmg cách dùng đa thức (polynomial) x+1.

Tổ hợp octet + parity là nền tảng để truyền đưa và lưu trữ trong kỹ thuật số. Vào những năm 1960 nó dẫn đến ra đời khối lưu trữ Băng ghi 9 đường dung lượng lớn, ghi 9 bit song song cho ra tốc độ truy cập nhanh ở thời kỳ đó.

Phát hiện lỗi[sửa | sửa mã nguồn]

Nếu một số lẻ lượng các bit (bao gồm cả bit chẵn lẻ), bị đảo lộn trong khi truyền thông một nhóm bit, thì bit chẵn lẻ sẽ có giá trị không đúng, và do đó báo hiệu rằng lỗi trong truyền thông đã xảy ra. Với lý do này, bit chẵn lẻ còn được gọi là một mã phát hiện lỗi, song nó không phải là một mã sửa lỗi, vì nó chẳng có cách nào xác định được vị trí của bit bị lỗi cả. Khi lỗi bị phát hiện, dữ liệu thu được phải bị bỏ đi và phải được truyền thông lại từ đầu. Trên kênh truyền có độ nhiễu cao, việc truyền tải dữ liệu thành công là một việc rất hao tốn thời gian, và đôi khi, việc truyền thông còn hầu như không thể thực hiện được nữa. Bit chẵn lẻ có một ưu điểm: nó là một mã tốt nhất chiếm chỉ một bit và chỉ dùng vài cổng XOR(XOR gate) để tạo giá trị mà thôi. Xin xem thêm mã Hamming để biết thêm về các mã sửa lỗi khác.

Ứng dụng[sửa | sửa mã nguồn]

Do đặc tính đơn giản của nó, bit chẵn lẻ được dùng trong rất nhiều ứng dụng phần cứng, những nơi mà việc tái diễn các thao tác khi có trục trặc xảy ra là một việc có thể thực hiện được, hoặc những nơi mà việc phát hiện lỗi đơn thuần là một việc có lợi. Lấy ví dụ, mạch nối SCSI (SCSI bus) dùng bit chẵn lẻ để phát hiện lỗi trong truyền thông, và rất nhiều các phần lưu trữ trong bộ nhớ các lệnh vi xử lý (microprocessor instruction cache) cũng dùng bit chẵn lẻ để bảo trợ hoạt động của nó nữa. Do các dữ liệu trong I-cache[2] chỉ là một bản sao của bộ nhớ chính (main memory), nội dung của nó có thể được xóa đi, nạp lại nếu dữ liệu ở trong chẳng may bị thoái hóa (corrupted).

Trong truyền dữ liệu nối tiếp (serial data transmission), dạng thức dữ liệu được dùng phổ thông nhất là dạng thức 7 bit, với một bit chẵn lẻ dùng quy tắc số chẵn, một Start bit và một hoặc hai Stop bit để đánh dấu/đồng bộ điểm bắt đầu cũng như kết thúc một byte dữ liệu trong chuỗi bit trên đường truyền. Dạng thức này thích ứng hầu hết các dạng thức 7-bit ký tự ASCII dưới hình thức byte 8-bit. Một byte dữ liệu trên đường truyền nối tiếp sẽ gồm 01 Start bit (bắt đầu), 7 bit dữ liệu, một parity bit và 01 Stop bit (kết thúc). Byte là một hình thức tiện lợi để biểu đạt dữ liệu. Những dạng thức khác cũng có thể thực hiện được, như dạng thức 8 bit dữ liệu cộng với một bit chẵn lẻ có thể dùng để chuyên chở tất cả các giá trị byte 8-bit.

Trong ngữ cảnh của truyền thông nối tiếp (serial communication), bit chẵn lẻ thường được phát sinh và kiểm tra bởi phần cứng giao thức - chẳng hạn như UART - và khi thu nhận, CPU có thể sử dụng kết quả nhận được (và hệ điều hành nữa) thông qua bit báo tình hình (status bit) trong thanh ghi của phần cứng giao thức. Việc khôi phục lại sau khi tình trạng lỗi xảy ra thường được thi hành bằng cách tái truyền dữ liệu, và chi tiết của việc này thường là do phần mềm phụ trách (ví dụ dùng các thường trình nhập/xuất (I/O routine) của hệ điều hành).

Khối chẵn lẻ[sửa | sửa mã nguồn]

Khối chẵn lẻ (parity block) được dùng trong một số cấu hình RAID,[3] và bằng cách dùng các khối chẵn lẻ, người ta đạt được tính dư thừa. Nếu một trong các ổ đĩa ở trong dãy đĩa bị hỏng, người ta có thể dùng các khối dữ liệu và các khối chẵn lẻ trong các đĩa còn làm việc để kiến tạo lại dữ liệu bị thất lạc (dữ liệu này nguyên ở trong cái đĩa bị hỏng).

Trong biểu đồ vẽ sẵn dưới đây, mỗi cột là biểu tượng của một ổ đĩa. Giả sử A1 = 00000111, A2 = 00000101, và A3 = 0000000. Ap - phát sinh do xử lý XOR giữa A1, A2, và A3 - sẽ có giá trị bằng 00000010. Nếu ổ đĩa thứ hai bị hỏng và giá trị A2 không thể truy cập được, thì giá trị này có thể được kiến tạo lại bằng xử lý XOR A1, A3, và Ap như sau:

A1 XOR A3 XOR Ap = 00000101

 RAID Array
A1  A2  A3
Ap  B1  B2
Bp  C1  C2
C3  C4  Cp

Lưu ý: Các khối dữ liệu được đánh dấu theo hình thức A# (# ám chỉ một con số), khối chẵn lẻ là Ap (p = parity).

Tham khảo[sửa | sửa mã nguồn]

  1. ^ Ziemer, RodgerE.; Tranter, William H. Principles of communication: systems, modulation, and noise . Hoboken, New Jersey. ISBN 9781118078914. OCLC 856647730.
  2. ^ I-cache - hay Instruction cache (Bộ trữ vi lệnh) - là một bộ nhớ trung gian giữa bộ nhớ ngoại biên và bộ điều hành xử lý trung tâm. Khi mã lệnh được thi hành, các từ mã tại các địa chỉ mà các vi lệnh yêu cầu, được sao chép vào bộ trữ vi lệnh để bộ điều hành xử lý trung tâm có thể truy cập các vi lệnh một cách trực tiếp. Khi một mã lệnh được dùng thường xuyên trong một nhóm các mã lệnh của trình ứng dụng, việc lưu trữ các vi lệnh trong bộ trữ (cache) cho phép bộ điều hành xử lý trung tâm truy cập chúng với tốc độ cao hơn, và không phải truy cập chúng từ mạnh nối ngoại biên (external bus), tiết kiệm được thời gian và nâng cao công suất xử lý.
  3. ^ RAID là cái tên viết tắt trong tiếng Anh: Redundant Array of Independent Disks - tạm dịch là "Dãy đĩa dư độc lập" là một hình thức sử dụng nhiều ổ cứng cùng một lúc. Có nhiều cấu hình tổ chức cách dùng các ổ cứng. Một trong số các cấu hình thường dùng là cấu hình "phân tỏa" (stripped set) hay còn gọi là RAID 0, cấu hình "phản chiếu" (mirrored set) hay còn cọi là RAID 1, và cấu hình "phân tỏa dùng bit chẵn lẻ" (Stripped set with parity) hay còn gọi là RAID 5.

Liên kết ngoài[sửa | sửa mã nguồn]