Tài liệu Báo cáo môn học mạng không dây và di động đề tài mã hoá và kiểm soát lỗi (coding and error control)

TRƯƠNG ĐAI HOC ĐIÊN LƯC KHOA CÔNG NGHỆ THÔNG TIN BÁO CÁO MÔN HỌC MẠNG KHÔNG DÂY VÀ DI ĐỘNG ĐỀỀ TÀI: Mã hoá và kiểm soát lỗỗi (Coding and error control) Giảng viên hướng dẫỗn: TS. LỀ ANH NGỌC Sinh viên thực hiện: (Nhóm 4) Chuyên ngành: QUẢN TRỊ AN NINH MẠNG Khóa: 2018-2023 Ha Nội, tháng 11 năm 2019 1 MỤC LỤC 1. PHÁT HIỆN LỖI.......................................................................................................3 1.1. Khái niệm về lỗi..................................................................................................3 1.2. Phát hiện lỗi(Error Detection)...........................................................................3 a, Kiểm tra chẵn lẻ (Parity check – Vertical Redundancy Check – VRC)...........5 b, Kiểm tra phần dư tuần hoàn – Cyclic Redundancy Check (CRC)..................5 c, Đa thức (Polynomials).......................................................................................8 d, Logic kĩ thuật số..............................................................................................10 2. MÃ KHỐI SỬA LỖI...............................................................................................10 2.1. Nguyên tắc mã khối..........................................................................................13 2.2. Hamming Code.................................................................................................16 2.3. Mã vòng (Cyclic Codes)....................................................................................19 2.4. Mã BCH (mã Bose, Chaudhuri và Hocquenghem)........................................24 2.5. Mã Reed-Solomon.............................................................................................25 2.6. Xen kẽ khối (Block Interleaving).....................................................................25 3.MÃ XOẮN (CONVOLUTIONAL CODES)...........................................................26 3.1. Giải mã (Decoding)...........................................................................................28 3.2. Mã Turbo...........................................................................................................31 4. TRUY VẤN LẶP LẠI TỰ ĐỘNG (ARQ)..............................................................34 4.1. Luồng dữ liệu (Data Flow)...............................................................................34 4.2. Kiểm soát lỗi......................................................................................................38 KẾT LUẬN..................................................................................................................42 TÀI LIỆU THAM KHẢO............................................................................................43 NHẬT KÍ LÀM VIỆC NHÓM....................................................................................44 ĐÁNH GIÁ THÀNH VIÊN.........................................................................................45 2 1. PHÁT HIỆN LỖI 1.1. Khái niệm về lỗi Trong các hệ thống truyền tín hiệu số, một lỗi sảy ra khi 1 bit bị thay đổi giữa bên gửi và bên nhận. Đó là bên gửi gửi bit 1 nhưng bên nhận lại nhận được bit 0 và ngược lại. Nhìn chung có 2 kiểu lỗi có thể sảy ra đó là lỗi đơn (single error) và lỗi xuất hiện đột ngột. 1 lỗi đơn là 1 trạng thái lỗi biệt lập nó thay đổi 1 bit nhưng không ảnh hưởng các bit bên cạnh. Một lỗi xuất hiện đột ngột có độ dài B (bit) là 1 chuỗi B bit kề nhau trong đó bit đầu tiên bit cuối cùng và một số bit ở giữa 2 bit này là nhận được với lỗi. Một cách chính xác, IEEE Std 100 định nghĩa 1 lỗi xuất hiện đột ngột như là 1 nhóm các bit trong đó 2 bit lỗi liên tiếp luôn bị ngăn cách bởi 1 số x cho trước các bít chính xác. Bít lỗi cuối cùng trong 1 lỗi gián đoạn và bit lỗi đầu tiên trong lỗi gián đọan tiếp theo cũng được ngăn cách x hoặc nhiều hơn các bít chính xác. Lỗi đơn có thể sảy ra và được thể hiện như là sự thể hiện của nhiễu nhiệt khi tỷ số SNR bị giảm đáng kể dẫn đến bên nhận bị nhầm lẫn khi nhận 1 bit Lỗi gián xuất hiện đột ngột phổ biến hơn lỗi đơn và khó giải quyết hơn, Lỗi này thường bị gây ra bởi tạp nhiễu xung lực hoặc sự giảm âm (fading) trong môi trường mạng không dây (mobile wireless) Những tác động của lỗi xuất hiện đột ngột sẽ cao hơn với tốc độ truyền cao hơn. 1.2. Phát hiện lỗi(Error Detection) Giả sử rằng dữ liệu được truyền theo các chuỗi bít liên tiếp và được gọi là các frames. Khi đó các khả năng có thể sảy ra như sau: - Pb : Khả năng 1 bit nhận được là bị lỗi và còn được gọi là tỷ lệ bit lỗi (bit error rate – BER) - P1: Khả năng 1 frame nhận được không có lỗi - P2: Khả năng với 1 giải thuật phát hiện lỗi được sử dụng, 1 frame nhận được còn 1 hoặc nhiều lỗi không được phát hiện - P3: Khả năng với 1 giải thuật phát hiện lỗi được sử dụng, 1 frame nhận được với 1 hoặc nhiều bit lỗi đã được phát hiện và không có các bit lỗi không được phát hiện. Khi không có 1 phương tiện nào được sử dụng để phát hiện lỗi như vậy P3 bằng 0. Giả sử rằng số lượng bit trong 1 frame là F khi đó: P1=(1-Pb)F P2=1-P1 3 Trong đó F là số bit trên mỗi frame. Nói cách khác, xác suất mà một khung hình xuất hiện không có lỗi bit sẽ giảm khi xác suất xảy ra lỗi bit đơn tăng. Ngoài ra, xác suất mà một frame đến mà không có lỗi bit nào giảm khi tăng chiều dài frame; frame càng dài, càng có nhiều bit thì càng có nhiều bit và xác suất xảy ra lỗi trong số này càng cao. Ví dụ 8.1: 1 đối tượng xác định cho các kết nối ISDN (mạng tích hợp đa dịch vụ) là tỷ lệ bit lỗi trên kênh 64 kbps nên nhỏ hơn10-6 trong khoảng ít nhất 90% của 1 phút được quan sát. Giả sử trung bình 1 frame có lỗi bit không bị phát hiện xảy ra mỗi ngày trên kênh 64 kbps được sử dụng liên tục, giả định độ dài 1 frame là 1000 bits. Số lượng frames có thể được truyền trong 1 ngày lên tới 5.529 x 106 , mang lại tỷ lệ lỗi mong muốn là P2 = 1/(5.529 x 106) = 0.18 x 10-6 . Nhưng nếu giả sử Pb =10-6, thì P1 = (0.999999)1000 = 0.999 và do đó P 2 = 103, quá lớn để đáp ứng yêu cầu. Như vậy khả năng 1 frame nhận được không có bit lỗi giảm khi khả năng lỗi đơn tăng. Hơn nũa khả năng 1 frame nhận được không có bit lỗi giảm khi tăng độ dài của frame. Có nhiều kỹ thuật được dùng để phát hiện lỗi. Tất các các kỹ thuật này tuân thủ theo các nguyên tắc sau đây: Cho 1 frame gồm các bit, một số bit để tạo thành 1 mã phát hiện lỗi được thêm vào bởi transmitter. Mã phát hiện lỗi được tính toán như là 1 hàm của các bit khác đã được truyền. Thông thường, với 1 block gồm k bit dữ liệu, thuật toán phát hiện lỗi sinh ra một mã phát hiện lỗi gồm n-k bit, trong đó (n-k) k) được gọi là codeword, sử dụng bộ mã hóa FEC (sửa lỗi chuyển tiếp). code word sau đó được truyền đi; trong trường hợp truyền không dây, bộ điều biến tạo ra tín hiệu tương tự để truyền. Trong quá trình truyền, tín hiệu bị nhiễu có thể tạo ra lỗi bit trong tín hiệu. Khi nhận, tín hiệu đến được giải mã tạo ra một chuỗi bit tương tự như từ mã gốc nhưng có thể có lỗi. Khối này được chuyển qua bộ giải mã FEC, với một trong 4 kết quả có thể xảy ra: 1. Nếu không có lỗi bit, đầu vào của bộ giải mã FEC giống hệt với codeword gốc và bộ giải mã tạo ra khối dữ liệu gốc làm đầu ra. 2. Với 1 số lỗi nhất định, bộ giải mã có thể phát hiện và sửa các lỗi đó. Vì vậy, mặc dù khối dữ liệu đến khác với codeword được truyền, bộ giải mã FEC có thể ánh xạ khối này vào khối dữ liệu gốc. 3. Đối với lỗi nhất định, bộ giải mã có thể phát hiện nhưng không sửa lỗi. Trong trường hợp này, bộ giải mã chỉ báo lỗi không thể sửa. 4. Đối với 1 số lỗi hiếm gặp, bộ giải mã sẽ không phát hiện bất kỳ lỗi nào xảy ra và ánh xạ khối dữ liệu n-bit vào khối k-bit khác với khối k-bit gốc. 12 2.1. Nguyên tắc mã khối Khoảng cách Hamming d (v1, v2) giữa hai chuỗi nhị phân n-bit, v1 và v2 là số bit với v1 và v2 khác nhau. Ví dụ: v1 = 011011, v2 = 110001 thì d (v1, v2) = 3 Giả sử muốn truyền các khối dữ liệu có độ dài k bit. Thay vì truyền mỗi khối dưới dạng k bit, chúng ta ánh xạ từng chuỗi k-bit thành một nbit codeword duy nhất. Ví dụ 8.6. Với k = 2 và n = 5 Khối dữ liệu Từ mã 00 00000 01 00111 10 11001 11 11110 Giả sử một khối từ mã trả về mẫu bit là 00100. Đây không phải từ mã hợp lệ nên cần tìm lỗi. Không thể chắc chắn khối dữ liệu nào đã được gửi vì 1,2,3,4 hoặc cả 5 bit được truyền có thể đã bị hỏng do nhiễu. Tuy nhiên, chỉ cần một bit duy nhất thay đổiđể chuyển 00000 thành 00100, ba bit thay đổi để chuyển 11110 thành 00100 và phải mất bốn bit thay đổi để chuyển 11001 thành 00100. Do đó, có thể suy ra rằng từ mã có khả năng nhất đã được gửi là 00000 khối dữ liệu mong muốn là 00. Xét về khoảng cách Hamming: d(00000, 00100) = 1; d(00111, 00100) = 2; d(11001, 00100) = 4; d(11111, 00100) = 3 nếu nhận được một từ mã không hợp lệ, thì chọn từ mã hợp lệ gần. Điều này chỉ hoạt động nếu có một từ mã duy nhất hợp lệ ở mức tối thiểu từ mỗi từ mã không hợp lệ. Với những từ mã không hợp lệ, ta có bảng dưới đây: Từ mã Khoảng cách Từ mã Từ mã 13 Khoảng cách Từ mã khỗng hợp lệ nhỏ nhầết hợp lệ khỗng hợp lệ nhỏ nhầết hợp lệ Ví dụ trên minh họa các thuộc tính cần yếu của mã sửa lỗi khối. Một mã khối (n, k) mã hóa k bit dữ liệu thành n bit codeword. Do đó, mã khối tương đương với hàm mẫu vc = ƒ (vd), trong đó vd là vectơ của k bit dữ liệu và vc là vectơ của n bit codeword. Với mã khối (n, k), có 2k codeword hợp lệ trong tổng số 2n codeword khả thi. Tỷ lệ bit dư thừa trên bit dữ liệu, (n-k)/k, được gọi là sự dư thừa của mã, và tỷ lệ bit dữ liệu trên tổng số bit, k/n, là tốc độ mã hoá. Tốc độ mã hoá là thước đo của băng thông bổ sung cần thiết để mang dữ liệu ở cùng tốc độ dữ liệu như không có mã. Ví dụ, một tốc độ mã là 1/2 yêu cầu gấp đôi băng thông của một hệ thống chưa được giải mã để duy trì cùng tốc độ dữ liệu. Chẳng hạn ta có tỷ lệ mã là 2/5 và do đó yêu cầu băng thông gấp 2,5 lần băng thông cho một hệ thống chưa được giải mã. Ví dụ, nếu tốc độ dữ liệu đầu vào cho bộ mã hóa là 1 Mbps, thì đầu ra từ bộ mã hóa phải là tốc độ 2,5 Mbps để theo kịp. Đối với một mã bao gồm các codeword w1, w2, …, ws, trong đó s = 2k. , Khoảng cách dmin tối thiểu được xác định là: dmin = min ij [d(wi, wj)] Đối với một số nguyên dương t đã cho, nếu một mã thỏa mãn dmin  2t + 1, thì mã có thể sửa tất cả các lỗi bit lên đến và bao gồm cả lỗi của bit t. Nếu dmin  2t, thì tất cả các lỗi t - 1 bit có thể được sửa và lỗi của bit t có thể được phát hiện nhưng không được sửa. Ngược lại, bất kỳ mã nào mà các lỗi sai số  t được sửa nếu thỏa mãn dmin  2t + 1 và bất kỳ mã nào có tất cả các lỗi  t - 1 được sửa và tất cả các lỗi về độ trễ đều được phát hiện nếu thỏa mãn dmin  2t . 14 Một cách khác để tìm mối quan hệ giữa dmin và t là số lỗi tối đa có thể sửa được đảm bảo cho mỗi codeword thỏa mãn: dmin - 1 2 t =[ ] trong đó [x] là phần nguyên của x (ví dụ: [6.3] = 6). Nếu ta chỉ quan tâm đến việc phát hiện lỗi và không sửa lỗi, thì số lỗi t, có thể được phát hiện thỏa mãn: t = dmin -1 Cho rằng nếu xảy ra lỗi dmin, điều này có thể thay đổi một codeword hợp lệ thành một từ khác. Bất kỳ số lượng lỗi nào ít hơn dmin không thể cho ra kết quả là một codeword hợp lệ. Việc thiết kế một mã khối liên quan đến một số vấn đề. 1. Đối với giá trị của n và k, ta mong muốn giá trị lớn nhất có thể của dmin. 2. Mã phải tương đối dễ mã hóa và giải mã, đòi hỏi bộ nhớ và thời gian xử lý tối thiểu. 3. Số lượng bit bổ sung, (n - k), phải nhỏ, để giảm lượng băng thông. 4. Số lượng bit bổ sung, (n - k),phải lớn, để giảm bớt tỷ lệ lỗi. Thực tế, hai vấn đề cuối xung đột và phải đánh đổi. 15 Hình 8.6. Cách mã hóa để cải thiện hiệu năng hệ thỗếng. Trong hình 8.6, đường cong bên phải mô tả hệ thống điều chế tín hiệu chưa được giải mã; khu vực bóng mờ đại diện cho khu vực có thể đạt được cải thiện tiềm năng. Trong khu vực này, BER (tỷ lệ lỗi bit) nhỏ hơn đạt được cho Eb/N0 nhất định và ngược lại, đối với BER đã cho, Eb/N0 nhỏ hơn được yêu cầu. Đường cong khác là kết quả của một nửa tỷ lệ mã (số lượng dữ liệu như nhau và bit kiểm tra). Lưu ý, ở tỷ lệ lỗi 10-5, sử dụng mã hóa cho phép 1 mức giảm Eb/N0 là 2.77 dB. Mức giảm này được gọi là mức tăng mã hóa, được định nghĩa như 1 mức giảm, tính bằng đơn vị dB, trong Eb/N0 cần thiết để đạt được BER chỉ định của hệ thống mã hóa sửa lỗi so với hệ thống chưa được giải mã sử dụng cùng một bộ điều chế tín hiệu. Điều quan trọng rằng BER cho tỉ lệ thứ hai 1/2 đường cong là tỷ lệ lỗi không được sửa chữa và giá trị Eb là cơ năng trên mỗi bit dữ liệu.Vì tốc độ là 1/2, có hai bit trên kênh cho mỗi bit dữ liệu và cơ năng trên mỗi bit được mã hóa bằng một nửa số mũ trên mỗi bit dữ liệu hoặc giảm 3 dB. Nếu ta nhìn vào số mũ trên mỗi bit được mã hóa cho hệ thống, thì sẽ thấy rằng tỷ lệ lỗi bit là khoảng 2.4 x 10-2, or 0.024. 16 Cuối cùng, lưu ý dưới một ngưỡng nhất định củaEb/N0, sơ đồ mã hóa thực sự làm giảm hiệu suất. Trong Hình 8.6, ngưỡng cũ xảy ra ở khoảng 5,4 dB. Dưới ngưỡng, các bit kiểm tra bổ sung tăng chi phí hệ thống, làm giảm số mũ trên mỗi bit dữ liệu gây ra tăng lỗi. Trên ngưỡng, khả năng sửa lỗi của mã nhiều hơn bù cho việc giảm Eb, dẫn đến tăng mã hóa. Sau đây ta chuyển sang xem xét một số mã sửa lỗi khối cụ thể. 2.2. Hamming Code Mã Hamming là một họ của (n, k) khối mã sửa lỗi gồm các tham số sau: Độ dài khối: n = 2m - 1 Số lượng bit dữ liệu: k = 2m - m -1 Số lượng bit kiểm tra: n - k = m Khoảng cách tối thiểu: dmin = 3 trong đó m  3. Mã Hamming rất đơn giản và dễ phân tích nhưng hiếm khi được sử dụng. Ta bắt đầu với các mã này bởi vì chúng minh họa một số nguyên tắc cơ bản của mã khối. Mã Hamming được thiết kế để sửa lỗi bit đơn. Để bắt đầu, ta hãy xác định đoạn mã phải dài bao nhiêu. Cơ chế của mã Hamming có cấu trúc giống logic phát hiện lỗi được mô tả trong hình 8.1; nghĩa là, quá trình mã hóa bảo tồn k bit dữ liệu và thêm (n - k) các bit kiểm tra. Để giải mã, logic so sánh nhận đầu vào hai giá trị (n - k)-bits, một từ codeword và một từ sự tính toán được thực hiện trên các bit dữ liệu So sánh từng bit được thực hiện bằng cách lấy XOR đầu vào. Kết quả được gọi là syndrome word. Do đó, mỗi bit của syndrome là 0 hoặc 1 tùy theo việc có hay không đối xứng ở vị trí bit cho hai đầu vào. Syndrome word rộng (n - k) bit và có phạm vi từ 0 đến 2(n - k) - 1. Giá trị 0 chỉ ra không có lỗi nào được phát hiện, giá tri 2(n - k) - 1 để chỉ ra, nếu có một lỗi, bit nào lỗi. Hiện tại, bởi một lỗi có thể xảy ra trên k bit dữ liệu bất kì hoặc (n - k) bit kiểm tra, ta phải có: 2(n - k) - 1  k + (n - k) = n Phương trình trên đưa ra số lượng bit cần thiết để sửa một lỗi bit đơn trong một từ có chứa k bit dữ liệu. Bảng 8.1 liệt kê số lượng bit kiểm tra được yêu cầu cho các độ dài dữ liệu khác nhau. 17 Trong đó: Data bits: số lượng bit dữ liệu Check Bits: số lượng bit kiểm tra %Increase: % tăng Single/Double -Error Detection: Phá hiện lỗi đơn/ đôi. Để thuận tiện, ta tạo ra một syndrome với các đặc điểm sau:  Nếu syndrome đều 0s, không có lỗi nào được phát hiện.  Nếu syndrome chứa một và chỉ một bit, thì đã xảy ra lỗi ở một trong các bit kiểm tra. Nhưng sửa lỗi là không cần thiết.  Nếu syndrome chứa nhiều hơn một bit được đặt thành 1, thì giá trị của syndrome cho biết vị trí của bit dữ liệu bị lỗi. Bit dữ liệu này được đảo ngược để sửa. Để đạt được các đặc điểm này, các bit dữ liệu và kiểm tra được sắp xếp thành một khối n bit như sau. Đếm từ vị trí ít quan trọng nhất (ngoài cùng bên phải), các bit kiểm tra Hamming được chèn tại các vị trí bằng mũ của 2 [tức là, các vị trí 1,2,4, ..., 2 (n - k)]. Các bit còn lại là bit dữ liệu. Để tính toán các bit kiểm tra, mỗi vị trí dữ liệu có giá trị 1 được biểu thị bằng giá trị nhị phân bằng vị trí của nó; do đó, nếu bit thứ 9 là 1, giá trị tương ứng là 1001. Tất cả các vị trí sau đó được XOR với nhau để tạo ra các bit của mã Hamming.Tại đầu ra, tất cả các giá trị vị trí bit trong đó có 1 được XOR. Trong trường hợp này, XOR cả bit dữ liệu và bit kiểm tra. Vì các bit kiểm tra xảy ra tại các vị trí bit có công suất bằng 2, nên chúng ta có thể XOR tất cả các vị trí bit dữ liệu có giá trị là 1, cộng với mã Hamming được hình thành bởi các bit kiểm tra. Nếu kết quả của XOR bằng 0, không có lỗi nào được phát hiện. Nếu kết quả là khác không, thì kết quả là syndrome và giá trị của nó bằng với vị trí bit bị lỗi. 18 Ví dụ 8.7 Mã Hamming (8.4) được trình bày trong Bảng 8.2. Khối dữ liệu 8 bit là 00111001. Bốn trong số các bit dữ liệu có giá trị 1 (được tô đậm) và các vị trí bit của chúng được XOR để tạo mã Hamming 0111, là bốn chữ số kiểm tra. Toàn bộ khối được truyền đi là 001101001111. Giả sử không có tại bit dữ liệu 3, trong vị trí bit 6, chấp nhận lỗi và thay đổi từ 0101. Sau đó,Khối đã nhận là 001101001111. Mã hamming nhận được vẫn là 0111. Thực hiện XOR mã Hamming và tất cả các vị trí bit cho bit dữ liệu khác 0, kết quả là 0110. Kết quả khác không phát hiện lỗi và chỉ ra rằng lỗi nằm ở vị trí bit 6. (a)Khỗếi đã truyếần (b)Kiểm tra tnh toán bit trước khi truyếần (c) Khỗếi nhận được 19 (d) Kiểm tra tnh toán bit sau khi nhận Mã vừa được mô tả bên trên được gọi là mã sửa lỗi đơn (SEC). Một biến thể là mã sửa lỗi đơn, mã phát hiện lỗi kép (SEC-DED). Bảng 8.1 cho thấy, các mã này yêu cầu một bit bổ sung với mã SEC. Bit bổ sung là một bit chẵn lẻ trên toàn bộ khối mã. 2.3. Mã vòng (Cyclic Codes) Hầu hết các mã khối sửa lỗi đang được sử dụng đều được gọi là mã tuần hoàn. Đối với các mã như vậy, nếu chuỗi n-bit c = (c0, c1, ... , cn-1) là một từ mã hợp lệ, và (cn-1, c0, c1, …, cn-2) được hình thành bằng cách dịch chuyển theo chu kỳ sang phải cũng là một từ mã hợp lệ. Lớp mã này có thể mã hóa và giải mã dễ dàng bằng các thanh ghi dịch chuyển phản hồi tuyến tính (LSFRs). Ví dụ về mã vòng bao gồm Bose Chaudhuri - Hocquenhem (BCH) và mã ReedSolomon. Việc hoàn thành LFSR của bộ mã hóa sửa lỗi theo chu kỳ giống như mã phát hiện lỗi CRC, được mô tả trong Hình 8.4. Điểm khác biệt chính là mã CRC lấy đầu vào có độ dài tùy ý và tạo mã kiểm tra CRC có độ dài cố định, trong khi đó mã sửa lỗi theo chu kỳ lấy đầu vào có độ dài cố định (k bit) và tạo mã kiểm tra cũng có độ dài cố định ( n - k bits). Hình 8.7 cho thấy việc triển khai LFSR của bộ giải mã cho mã khối tuần hoàn. So sánh điều này với logic bộ mã hóa trong Hình 8.4. Lưu ý rằng đối với bộ mã hóa, k bit dữ liệu được coi là đầu vào để tạo mã (n k) của các bit kiểm tra trong thanh ghi dịch. Đối với bộ giải mã, đầu vào là luồng bit nhận được của n bit, bao gồm k bit dữ liệu, theo sau bởi (n k) bit kiểm tra. Nếu không có lỗi: sau k bước đầu tiên, thanh ghi dịch chứa mẫu bit kiểm tra được truyền đi. Sau (n - k) bước còn lại, nó gồm một mã hội chứng. Để giải mã môt mã tuần hoàn, quy trình sau được sử dụng: 20