Giáo trình Kỹ thuật truyền số liệu - Chương III: Truyền số liệu

dùng một mạch ghi dịch phản hồi về một cổng EXOR. Số lượng cột của bộ ghi dịch phụ thuộc vào giá trị C đã chọn cho G(x) và cũng là số bit cho mã CRC.
Hình vẽ cho ta mạch tạo CRC 3 bit.
Hình 3.52 Mạch tạo CRC dùng bộ ghi dịch với G(x)=x3-1.
Ví dụ 2: Ta cần truyền thông tin: 
M(x) = 1010001101 với hàm
G(x) = x5 + x4 + x2 + 1
Ta có mạch dịch và các bước thực hiện như hình vẽ.
Hình 3.53 Mạch ghi dịch với hàm G(x) = x5 + x4 + x2 + 1.
Người ta có thể tạo mã CRC dài 12 bit, 16 bit, 32 bit ... Vấn đề là chọn G(x) sao cho phù hợp. 
Thường cho 16 bit người ta chọn:
G(x) = x16 + x15 + x2 + 1
Hoặc G(x) = x16 + x12 + x5 + 1
Hình 3.54 Mạch dịch với G(x) = x16 + x15 + x2 + 1.
Mạch tạo CRC cho 16 bit như hình vẽ:
Trong mạng Ethernet, người ta truyền 1500 bytes cần CRC là 32 bit.
Và hàm G(x) được sử dụng là:
G(x) = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1
Và dùng Intel 82586 coprocessor on chip.
Từ những ví dụ trên ta có thể nhận xét một cách máy móc rằng: để tạo ra mạch dịch với các cổng EXOR và các FF cho một hàm có sẵn ở đầu vào các thành phần x có giá trị 1 sẽ có cổng EXOR, tín hiệu vòng về sẽ được đưa đến các mạch EXOR đó, số lượng các FF trong bộ ghi dịch là C đã chọn của hàm G(x).
3.8.3.4 Mã sửa sai - Mã Hamming
Vấn đề là: nếu khi mã hóa mỗi ký tự ta xử dụng n bit thì với n bit ta có được 2n ký tự. Nhưng nếu như vậy thì vấn đề tìm sai và sửa sai không thể thực hiện được.
Nếu ta thêm 1 bit để kiểm tra thì có thể tìm được những sai sót đơn giản (như VRC, LRC).
Ông Hamming của phòng thí nghiệm Bell đưa ra một đề án về mã khoảng cách.
Theo Hamming: khoảng cách Hamming giữa 2 từ mã bằng số lượng bit khác nhau giữa chúng.
Ví dụ: 
B = 1000010 
C = 1000011 Khoảng cách là 1
Nếu có P ® B = 01000010
C = 11000011 Khoảng cách là 2
Điều đó cho ta khả năng ở bộ thu sau khi kiểm tra có thể sửa sai trong một giới hạn nào đó bit sai.
Hamming đã phát triển nó thành mã Hamming. Để có thể thấy được rõ ràng tác dụng đó, ta có thể lấy ví dụ cho hệ 16 (016 ¾ F16). Thông thường để biểu thị từ 0 – F ta chỉ cần 4 bit. Nếu dùng 7 bit để biểu thị, ở bộ thu chúng ta có thể phát hiện được 2 bit sai và có thể sửa từng bit.
7 bit của từ mã bao gồm: 4 bit biểu thị thông báo m3 m2 m1 m0 và 3 bit kiểm tra C2 C1 C0.
Mỗi từ mã có dạng m3 m2 m1 C2 m0 C1 C0 .
Các giá trị của C2 C1 C0 được tính như sau:
C0 = m0 Å m1 Å + m3
C1 = m0 Å m2 Å + m3
C2 = m1 Å m2 Å + m3
Ví dụ: mã cho chữ A16 là: m3 m2 m1 m0 = 1010 (A16 ) 
C0 = 0 Å 1 Å 1 = 0
C1 = 0 Å 0 Å 1 = 1
C2 = 1 Å 0 Å 1 = 0
Vậy A theo mã Hamming là: 1010010
Khi bộ phận thu thu được một từ mã, có thể tính lại 3 giá trị kiểm tra: P0; P1; P2 như sau:
P0 = C0 Å m0 Å m1 Å + m3
P1 = C1 Å m0 Å m2 Å + m3
P2 = C2 Å m1 Å m2 Å + m3
Nếu P0 = P1 = P2 = 0 thì phép truyền không gây sai số. Nếu có sai ta dựa vào giá trị nhị phân của P2; P1; P0 mà xác định vị trí sai.
Ví dụ: ta nhận được thông tin 1110010
Ta có:
P0 = 0 Å 0 Å 1 Å 1 = 0
P1 = 1 Å 0 Å 1 Å 1 = 1 110 Þ 6
P2 = 0 Å 1 Å 1 Å 1 = 1
Vậy bit thứ 6 sai.
3.8.4 Kiểm tra sai (Error control)
Kiểm tra sai dùng để kiểm tra, tìm và sửa sai trong frames được truyền.
Trước tiên, dữ liệu được truyền tạo thành các frames và truyền liên tiếp các frames với nhau. Frames đến đồng thời hay đến lần lượt khi truyền, mỗi frames bảo đảm sự độc lập và giá trị cố định khi nhận. Ta thấy có 2 loại sai:
Mất frame: 1 frame bị mất trước khi đến bên kia hoặc nhiễu làm cho frame hư, làm cho bộ nhận cho rằng frame chưa truyền.
Frame bị hư: Frame được xác định đến mà một số bit bị sai trong khi truyền.
Hầu hết các kỹ thuật hiện nay cho việc kiểm tra sai dựa trên cơ sở sau:
Phát hiện sai: như phần trước ta dùng FCS để kiểm tra mà nội dung chính là tìm CRC.
Sự thừa nhận tích cực: Bộ phận nhận truyền tín hiệu ACK tích cực khi có kết quả, frame không có sai.
Truyền lại sau thời gian nghỉ: nguồn sẽ truyền lại một frame nào đó mà chưa có được ACK, trước khi kết thúc thời gian truyền.
Sự thừa nhận không tích cực và truyền lại: Bộ phận nhận trả lại tín hiệu NAK khi có một frame nào đó có sai, nguồn sẽ truyền lại frame đó.
Tổng hợp lại ta dùng phương pháp yêu cầu phát lại ARQ (Automatic Repeat reQuest). ARQ có 3 loại:
Dừng và chờ ARQ.
Trở lại N, ARQ.
Truyền lại có lựa chọn ARQ.
Tất cả dạng đó đều dựa vào kỹ thuật kiểm tra dòng mà ta đã mô tả.
3.8.4.1 Dừng và chờ ARQ (Stop and wait ARQ): 
Dừng và chờ ARQ dựa trên kỹ thuật kiểm tra lưu thông. Nó được miêu tả như hình vẽ 5-11.
Trạm nguồn truyền một frame đơn giản và nó chờ tín hiệu ACK. Các frame khác không được truyền cho đến khi trạm nhận cung cấp tín hiệu đó cho trạm nguồn.
Frame được truyền do nguồn có thể mất hoặc sai, nếu như bộ phận nhận phát hiện sai, nó bỏ frame đó và truyền tín hiệu NAK.
Do đó nguồn truyền lại frame bị hư. Mặt khác, nếu frame nguồn bị mất do nhiễu thì bộ phận thu không cho trả lời, nguồn phải chờ một thời gian. Sau mỗi frame được truyền, nguồn chờ ACK hoặc NAK. Nếu không nhận được ACK trong thời gian dừng chờ thì frame đó được truyền lại. Chú ý rằng nguồn sẽ giữ lại một copy của frame truyền cho đến khi nó nhận được ACK.
Hình 3.55 ARQ dừng và chờ.
Một điều nữa cần phải nhắc trước khi kết thúc vấn đề là: Nếu một frame truyền đúng mà trong khi truyền ACK bị hư thì sau thời gian dừng chờ không có tín hiệu ACK nguồn sẽ truyền lại frame đó. Bộ phận nhận bây giờ sẽ nhận 2 bản sao của một frame. Để tránh vấn đế đó, frame luôn thay đổi giá trị 0 và 1: ta có ACK0 và ACK1. ACK0(ACK1) nhận được của frame 1(0) và chỉ ra rằng bộ phận nhận đã sẵn sàng cho frame 0(1).
Về nguyên tắc, dừng và chờ ARQ có ưu điểm là đơn giản. (Nhược điểm ta đã thảo luận ở trên).
3.8.4.2 Trở lại N-ARQ (Goback N- ARQ): 
Một phương án của ARQ tiếp tục là trở lại N-ARQ: Với kỹ thuật này một trạm có thể gửi đi một loạt các frames với các khung cửa sổ trượt sử dụng cho kỹ thuật kiểm tra dòng. Khi mà không có sai thì bộ phận nhận sẽ dùng ACK.
Giả thiết là trạm A gửi một số frames sang B. Sau mỗi lần truyền 1 frame A thiết lập tín hiệu ACK. Kỹ thuật trở về N đưa vào những khả năng có thể xảy ra sau:
* Mất frame: có 3 trường hợp.
A truyền frame thứ i đến B.
B phát hiện ở frame có sai.
B gửi NAK i chỉ rằng frame i phải truyền lại. Khi A nhận được NAK frame thứ i và tất cả các frames tiếp theo đều phải truyền lại. 
Frame i bị mất trong khi truyền, frame(i+1) sẽ gửi đi. B nhận frame(i+1) không đúng thứ tự ® gửi NAKi đến A. 
Frame i bị mất trong khi truyền nhưng sau đó A không truyền frame (i+1). B không nhận được gì và trả lại ACK hay NAK. A sẽ dừng và sau thời gian qui định nó truyền lại frame i. 
* Mất ACK: Có 2 trường hợp.
B nhận được frame i và truyền ACK(i+1) và nó bị mất trong khi truyền.
Hình vẽ chỉ cho ta các dòng frame cho phương pháp trở lại N-ARQ trên đường truyền full - duplex. Ta cho rằng có 3 bit để chỉ thứ tự frame (0-7).
Với phương pháp trở lại N-ARQ, không yêu cầu sau khi gửi đi một frame phải có ACK. Ví dụ trạm A gửi các frames 0,1,2,3 và trạm B sẽ trả lời với ACK1 sau khi nhận frame 0 nhưng nó chưa trả lời cho frame 1 và 2. Sau khi nhận frame 3, B sẽ gửi ACK4 chỉ ra rằng tất cả các frame khác được chấp nhận.
Hình 3.56 Trở lại N-ARQ.
Trường hợp frame 2 bị sai. B sẽ gửi NAK2 đến A cho dù frames 3,4,5 đã gửi đi nhưng A sẽ truyền lại từ frame 2, frames 3,4,5 đã nhận sẽ bị hủy bỏ. 
Bây giờ chúng ta làm rõ vấn đề vì sao ta có 2n mà độ lớn cửa sổ chỉ 2n-1. Đó là do ảnh hưởng lẫn nhau của kiểm tra sai và ACK. Một trạm sẽ gửi ACK với frame. Do độ dài ACK có n bits trong frame khi gửi frame đi thì ACK đầu tiên bị mất, có thể ACK tiếp theo qua. Ta giả thiết nếu trạm truyền frame 0 và nhận ACK1 với truyền frame 1,2,3,4,5,6,7,0 và nhận các ACK khác. Điều đó có nghĩa là 8 frames đều nhận đúng và trạm nhận bắt đầu lại ACK1.
3.8.4.3 Truyền lại có lựa chọn ARQ (Selective Reject ARQ): 
Hình 3.57 ARQ có lựa chọn.
Với sự truyền lại có lựa chọn ARQ khi phát hiện sai ta chỉ truyền lại frame nào mà ta nhận được NAK hoặc với thời gian tạm nghỉ. 
Ta thấy sự sai hoàn toàn giống như trường hợp trước mà nó truyền lại có lựa chọn. So với trở lại N-ARQ nó hiệu quả hơn nhiều vì nó chỉ truyền lại frame hư, ít tốn thời gian hơn. Mặc khác, bộ phận thu cần giử lại frame hư có NAK cho đến khi nó được truyền lại vì nó có giá trị logic cho frame mới đưa vào theo thứ tự. Sự truyền lại sẽ yêu cầu phức tạp hơn khi ta gửi các frame không theo thứ tự. Do sự phức tạp đó mà phương thức truyền lại có lựa chọn ít được xử dụng.
Ta giả thiết frame 2 bị sai, do sự làm trể khi truyền. Frame bị sai mãi đến sau khi truyền frames 3,4,5 mới tới bộ thu. Nếu theo giải thuật trở lại N-AKQ thì các frame đó bị bỏ đi và buộc phải truyền lại. Với giải thuật truyền lại có lựa cọn ARQ, các frames đó được giử lại ở bộ phận thu. Chú ý rằng trong trường hợp tiếp theo, các frames không thê ACK ngoài thứ tự. Có nghĩa là frame 2 sau khi truyền lại, sau khi bộ thu đã cho ACK6 mới cho ACK3, ACK4, ACK5 được.