Thiết Kế & Thi Công Mã Hóa Kênh FPGA Tăng Độ Tin Cậy Thông Tin Vô Tuyến (ĐH SPKT TP.HCM)

Thiết kế, thi công bộ mã hóa kênh FPGA tăng độ tin cậy thông tin vô tuyến. Giải pháp nâng cao chất lượng truyền dẫn, giảm thiểu lỗi hiệu quả.

Người đăng

Ẩn danh

Thể loại

Công trình nghiên cứu khoa học của sinh viên

2022

61
1
0

Phí lưu trữ

30 Point

Tóm tắt

I. Mã Hóa Kênh FPGA Giải Pháp Tối Ưu Hóa Độ Tin Cậy Dữ Liệu

Trong kỷ nguyên số, việc truyền tải thông tin chính xác và toàn vẹn đóng vai trò nền tảng. Các hệ thống thông tin, đặc biệt là thông tin vô tuyến, liên tục đối mặt với các yếu tố gây nhiễu, dẫn đến nguy cơ sai lệch dữ liệu. Để giải quyết vấn đề này, các kỹ thuật mã hóa kiểm soát lỗi (Error Control Coding - ECC) đã ra đời. Trong số đó, phương pháp Mã Hóa Kênh FPGA nổi lên như một giải pháp hiệu quả, kết hợp sức mạnh xử lý song song của công nghệ FPGA (Field Programmable Gate Array) và sự đơn giản, hiệu quả của các thuật toán mã hóa kênh. Công nghệ FPGA cho phép hiện thực hóa các thuật toán phức tạp thành phần cứng chuyên dụng, mang lại tốc độ xử lý vượt trội và độ trễ thấp so với các giải pháp dựa trên phần mềm. Việc áp dụng Mã Hóa Kênh FPGA giúp các hệ thống truyền thông không chỉ phát hiện mà còn có khả năng sửa lỗi, đảm bảo độ tin cậy thông tin được nâng cao một cách đáng kể. Nghiên cứu về 'Thiết kế và thi công bộ mã hóa kênh theo công nghệ FPGA' đã chứng minh tính khả thi và hiệu quả của hướng tiếp cận này, đặc biệt khi triển khai thuật toán Mã CRC (Cyclic Redundancy Check) trên nền tảng phần cứng. Giải pháp này không chỉ có ý nghĩa học thuật mà còn mở ra nhiều ứng dụng thực tiễn trong các giao thức truyền thông hiện đại.

1.1. Tầm quan trọng của tính toàn vẹn dữ liệu trong hệ thống số

Tính toàn vẹn dữ liệu là yếu tố sống còn trong mọi hệ thống kỹ thuật số. Dữ liệu là nền tảng cho mọi hoạt động, từ giao tiếp giữa các thiết bị lưu trữ như USB, ổ cứng với máy tính, đến trao đổi thông tin giữa CPU và RAM. Bất kỳ một sai sót nào, dù là nhỏ nhất, trong quá trình truyền và nhận đều có thể gây ra hậu quả nghiêm trọng. Ví dụ, một bit lỗi trong một tệp chương trình có thể làm sập toàn bộ hệ thống. Trong thông tin vô tuyến, dữ liệu bị ảnh hưởng bởi nhiễu, suy hao tín hiệu và các vật cản, làm tăng xác suất lỗi. Do đó, việc trang bị một cơ chế kiểm soát lỗi mạnh mẽ là yêu cầu bắt buộc. Các mô hình mã hóa kênh như mã CRC được thiết kế để thêm các bit kiểm tra (redundancy bits) vào dữ liệu gốc. Bên nhận sẽ sử dụng các bit này để xác minh tính chính xác của thông tin nhận được. Điều này đảm bảo rằng dữ liệu không bị thay đổi trong suốt quá trình truyền, duy trì độ tin cậy thông tin ở mức cao nhất.

1.2. Giới thiệu công nghệ FPGA và vai trò trong việc mã hóa kênh

FPGA là một loại vi mạch tích hợp cho phép người dùng lập trình cấu trúc phần cứng sau khi sản xuất. Khác với CPU hoạt động tuần tự, FPGA có khả năng thực thi các tác vụ song song, lý tưởng cho các ứng dụng đòi hỏi xử lý tín hiệu tốc độ cao và độ trễ thấp. Trong lĩnh vực mã hóa kênh, FPGA đóng vai trò là nền tảng lý tưởng để hiện thực hóa các thuật toán như Mã CRC. Thay vì chạy thuật toán trên phần mềm, việc thiết kế trực tiếp trên phần cứng FPGA bằng ngôn ngữ mô tả phần cứng như Verilog HDL cho phép tạo ra một bộ mã hóa/giải mã chuyên dụng. Giải pháp Mã Hóa Kênh FPGA này hoạt động nhanh hơn, hiệu quả hơn và tiêu thụ ít tài nguyên hệ thống hơn so với việc dùng CPU. Nghiên cứu đã tập trung vào việc thi công bộ mã hóa CRC-16 trên kit FPGA Xilinx AX309, chứng tỏ khả năng tích hợp và ứng dụng thực tiễn của công nghệ này để tăng cường độ tin cậy thông tin.

II. Thách Thức Trong Thông Tin Vô Tuyến Vấn Đề Nhiễu Và Lỗi

Môi trường truyền dẫn vô tuyến vốn không hoàn hảo. Tín hiệu khi lan truyền trong không gian phải đối mặt với vô số thách thức có thể làm suy giảm chất lượng và gây ra lỗi dữ liệu. Các nguồn gây lỗi rất đa dạng, bao gồm nhiễu điện từ tự nhiên, sự phản xạ tín hiệu từ các vật thể, và sự suy hao do khoảng cách. Những yếu tố này làm thay đổi các bit thông tin, biến '0' thành '1' và ngược lại, gây ra sai lệch giữa dữ liệu gửi và dữ liệu nhận. Vấn đề này đặc biệt nghiêm trọng trong các ứng dụng yêu cầu độ chính xác cao như hệ thống điều khiển công nghiệp, truyền thông mạng, hay các thiết bị nhúng. Nếu không có cơ chế kiểm soát hiệu quả, các lỗi này có thể tích tụ và dẫn đến hỏng hóc toàn bộ gói tin, buộc hệ thống phải truyền lại, làm giảm thông lượng và tăng độ trễ. Do đó, việc phát triển các phương pháp phát hiện lỗi và sửa lỗi là một yêu cầu cấp thiết. Các kỹ thuật Mã Hóa Kênh FPGA cung cấp một lớp bảo vệ vững chắc, giúp hệ thống chống lại những tác động tiêu cực từ kênh truyền, từ đó đảm bảo độ tin cậy thông tin và hiệu suất hoạt động ổn định.

2.1. Phân tích các dạng lỗi phổ biến trong quá trình truyền dữ liệu

Lỗi trong truyền dữ liệu thường được phân thành hai loại chính: lỗi bit đơn và lỗi bệt (lỗi chùm). Lỗi bit đơn là trường hợp một bit riêng lẻ trong chuỗi dữ liệu bị đảo giá trị. Lỗi này thường xảy ra do nhiễu trắng hoặc nhiễu nhiệt có tính ngẫu nhiên. Trong khi đó, lỗi bệt (burst error) là tình trạng một chuỗi các bit liên tiếp bị lỗi. Dạng lỗi này phổ biến hơn trong các kênh truyền vô tuyến, gây ra bởi các hiện tượng như fading (suy hao tín hiệu nhanh) hoặc nhiễu xung đột. Các thuật toán phát hiện lỗi khác nhau có hiệu quả khác nhau với từng loại lỗi. Nghiên cứu cho thấy mã CRC đặc biệt hiệu quả trong việc phát hiện các lỗi bệt, vốn là một thách thức lớn. Khả năng phát hiện lỗi của mã CRC phụ thuộc rất nhiều vào việc lựa chọn đa thức sinh (generator polynomial) phù hợp. Một đa thức sinh được chọn tốt có thể phát hiện tất cả các lỗi bệt có độ dài nhỏ hơn hoặc bằng bậc của nó.

2.2. Hậu quả của sai sót dữ liệu đối với hiệu suất giao thức truyền thông

Sai sót dữ liệu ảnh hưởng trực tiếp đến hiệu suất của các giao thức truyền thông như USB, Modbus, hay Ethernet. Khi một gói tin bị lỗi được phát hiện, cơ chế ARQ (Automatic Repeat Request) thường được kích hoạt, yêu cầu bên gửi phải truyền lại toàn bộ gói tin đó. Quá trình này tiêu tốn băng thông và làm tăng độ trễ của hệ thống. Trong các ứng dụng thời gian thực, độ trễ cao là điều không thể chấp nhận. Hơn nữa, nếu cơ chế phát hiện lỗi không đủ mạnh, các gói tin lỗi có thể bị bỏ sót và được xử lý như dữ liệu đúng, dẫn đến các quyết định sai lầm ở tầng ứng dụng. Ví dụ, trong chuẩn USB 2.0, các gói dữ liệu được bảo vệ bằng CRC-16 để ngăn chặn dữ liệu hỏng được gửi qua bus. Việc triển khai một bộ mã hóa CRC hiệu quả trên FPGA giúp giảm thiểu tỷ lệ lỗi, tăng thông lượng hữu ích và đảm bảo hoạt động ổn định cho toàn bộ hệ thống nhúng.

III. Nguyên Lý Mã CRC Phương Pháp Phát Hiện Lỗi Truyền Dữ Liệu Hiệu Quả

Mã CRC (Cyclic Redundancy Check) là một trong những kỹ thuật phát hiện lỗi được sử dụng rộng rãi nhất trong các hệ thống truyền thông kỹ thuật số. Nguyên lý cơ bản của nó dựa trên phép chia đa thức trong trường nhị phân. Dữ liệu cần truyền được xem như một đa thức, sau đó được chia cho một đa thức cố định gọi là đa thức sinh. Phần dư của phép chia này, được gọi là chuỗi CRC, sẽ được đính kèm vào cuối dữ liệu gốc và truyền đi. Tại bên nhận, toàn bộ gói tin (dữ liệu + CRC) lại được chia cho cùng một đa thức sinh. Nếu phần dư bằng không, dữ liệu được coi là chính xác. Ngược lại, nếu phần dư khác không, điều đó cho thấy đã có lỗi xảy ra trong quá trình truyền. Ưu điểm lớn của mã CRC là sự đơn giản trong việc triển khai phần cứng bằng các cổng XOR và thanh ghi dịch, rất phù hợp với kiến trúc của FPGA. Nghiên cứu đã tập trung vào CRC-16 với đa thức sinh g(x) = x¹⁶ + x¹⁵ + x² + 1, một chuẩn phổ biến trong các ứng dụng như Modbus và USB.

3.1. Cơ chế hoạt động của phép chia đa thức trong thuật toán CRC

Trong thuật toán CRC, chuỗi bit dữ liệu M(x) được xử lý như một đa thức với các hệ số nhị phân. Trước khi thực hiện phép chia, M(x) được nhân với x^r, với r là bậc của đa thức sinh G(x). Thao tác này tương đương với việc thêm r bit 0 vào cuối chuỗi dữ liệu. Sau đó, đa thức kết quả x^r * M(x) được chia cho G(x) bằng phép chia modulo-2 (tương đương phép toán XOR). Phần dư R(x) thu được từ phép chia này chính là chuỗi CRC. Từ mã cuối cùng được truyền đi là T(x) = x^r * M(x) + R(x). Tại bên nhận, T(x) được chia cho G(x). Do x^r * M(x) = Q(x) * G(x) + R(x), ta có T(x) = Q(x) * G(x). Vì vậy, nếu không có lỗi, T(x) sẽ chia hết cho G(x) và cho phần dư bằng 0. Cơ chế này đảm bảo khả năng phát hiện lỗi một cách toán học và có hệ thống.

3.2. Vai trò của đa thức sinh trong việc xác định hiệu quả mã hóa

Hiệu quả của mã CRC phụ thuộc hoàn toàn vào việc lựa chọn đa thức sinh G(x). Một đa thức sinh tốt phải có khả năng phát hiện được nhiều loại lỗi nhất có thể. Các tiêu chí để chọn một đa thức sinh mạnh bao gồm: không chia hết cho x (để phát hiện lỗi 1 bit), và là một đa thức nguyên thủy (để tối đa hóa khả năng phát hiện lỗi bệt). Đa thức sinh g(x) = x¹⁶ + x¹⁵ + x² + 1 được sử dụng trong nghiên cứu là một chuẩn của ANSI và được ứng dụng rộng rãi. Nó có khả năng phát hiện: tất cả các lỗi 1 bit và 2 bit, tất cả các lỗi với số bit lẻ, và tất cả các lỗi bệt có độ dài lên đến 16 bit. Việc lựa chọn đúng đa thức sinh là yếu tố then chốt để đảm bảo độ tin cậy thông tin và tận dụng tối đa sức mạnh của thuật toán CRC.

IV. Hướng Dẫn Thiết Kế Bộ Mã Hóa Kênh FPGA Với Mã CRC 16

Việc hiện thực hóa bộ mã hóa kênh trên FPGA đòi hỏi một quy trình thiết kế bài bản, từ phân tích lý thuyết đến mô phỏng và triển khai trên phần cứng. Nghiên cứu đã trình bày chi tiết quá trình thiết kế và thi công bộ mã hóa và giải mã CRC-16 bằng ngôn ngữ mô tả phần cứng Verilog HDL. Thiết kế này được tối ưu để hoạt động với tần số xung nhịp 50 MHz. Cấu trúc tổng thể của bộ mã hóa được chia thành các khối chức năng rõ ràng, giúp dễ dàng quản lý và kiểm tra. Trái tim của thiết kế là khối thực hiện phép chia đa thức, được xây dựng từ các thanh ghi dịch và cổng logic XOR, phản ánh trực tiếp cấu trúc toán học của thuật toán CRC. Toàn bộ quá trình được mô phỏng và tổng hợp bằng phần mềm chuyên dụng Xilinx ISE, đảm bảo thiết kế hoạt động chính xác trước khi được nạp vào kit FPGA vật lý. Cách tiếp cận này cho phép tạo ra một giải pháp Mã Hóa Kênh FPGA hiệu năng cao, sẵn sàng tích hợp vào các hệ thống nhúnggiao thức truyền thông thực tế.

4.1. Quy trình thiết kế bộ mã hóa và giải mã sử dụng Verilog HDL

Verilog HDL là ngôn ngữ tiêu chuẩn để mô tả các mạch điện tử số. Quá trình thiết kế bắt đầu bằng việc chuyển đổi lưu đồ thuật toán CRC thành các module Verilog. Bộ mã hóa (Encoder) được thiết kế để nhận một khối dữ liệu đầu vào, nối thêm 16 bit 0, sau đó thực hiện quá trình dịch bit và XOR để tính toán ra mã CRC 16 bit. Mã CRC này sau đó được ghép với dữ liệu gốc để truyền đi. Ngược lại, bộ giải mã (Decoder) nhận toàn bộ khối dữ liệu (gồm cả CRC), thực hiện lại phép chia và kiểm tra xem phần dư có bằng 0 hay không. Thiết kế được mô tả ở mức RTL (Register-Transfer Level), tập trung vào dòng chảy dữ liệu giữa các thanh ghi, giúp công cụ tổng hợp của Xilinx ISE có thể tự động tạo ra cấu trúc mạch logic tối ưu.

4.2. Cấu trúc và chức năng các khối Counter và Shifter_encode

Thiết kế bộ mã hóa CRC-16 trong nghiên cứu bao gồm hai khối chính: CounterShifter_encode. Khối Counter có nhiệm vụ đếm số chu kỳ xung nhịp cần thiết để hoàn thành quá trình dịch chuyển toàn bộ bit dữ liệu. Nó tạo ra các tín hiệu điều khiển, chẳng hạn như tín hiệu cho phép en_crc, báo hiệu khi nào quá trình tính toán CRC hoàn tất. Khối Shifter_encode là nơi thực hiện logic cốt lõi. Nó chứa một thanh ghi dịch 16-bit và các cổng XOR được kết nối theo cấu trúc của đa thức sinh g(x) = x¹⁶ + x¹⁵ + x² + 1. Tại mỗi xung nhịp, một bit dữ liệu mới được đưa vào và thanh ghi được dịch đi một vị trí, đồng thời thực hiện các phép XOR cần thiết. Sau khi tất cả các bit dữ liệu đã được xử lý, giá trị còn lại trong thanh ghi chính là mã CRC.

V. Đánh Giá Hiệu Năng Mã Hóa Kênh FPGA Qua Các Testcase Thực Tế

Để xác minh hiệu quả của bộ Mã Hóa Kênh FPGA đã thiết kế, một loạt các kịch bản kiểm thử (testcase) đã được xây dựng và thực hiện. Các testcase này mô phỏng những tình huống hoạt động thực tế, bao gồm việc truyền dữ liệu theo các giao thức truyền thông phổ biến như USB 2.0 và Modbus, với các độ dài khối dữ liệu khác nhau. Hiệu năng của thiết kế được đánh giá dựa trên nhiều tiêu chí: thời gian tính toán, tài nguyên FPGA sử dụng, và quan trọng nhất là khả năng phát hiện lỗi. Các kịch bản lỗi được tạo ra một cách có chủ ý, từ lỗi 1 bit, 2 bit đến các lỗi phức tạp hơn, nhằm kiểm tra giới hạn của bộ giải mã CRC-16. Kết quả mô phỏng trên phần mềm Xilinx ISE và kiểm tra trên kit FPGA vật lý cho thấy thiết kế hoạt động đúng như mong đợi, đáp ứng các yêu cầu về tốc độ và có khả năng phát hiện lỗi rất cao, khẳng định giá trị thực tiễn của giải pháp trong việc nâng cao độ tin cậy thông tin.

5.1. Kết quả mô phỏng với các chuẩn truyền thông USB 2.0 và Modbus

Nghiên cứu đã tiến hành mô phỏng với các khối dữ liệu có độ dài tiệm cận với ứng dụng thực tế. Với chuẩn USB 2.0, khối dữ liệu 4000 bit đã được sử dụng. Bộ mã hóa đã tính toán thành công mã CRC-16 trong khoảng 80.34 micro giây. Tương tự, với chuẩn Modbus sử dụng khối dữ liệu 1600 bit, thời gian tính toán là 32.34 micro giây. Các dạng sóng kết quả cho thấy bộ mã hóa và giải mã hoạt động chính xác, tạo ra đúng mã CRC và xác thực được các gói tin không lỗi. Các thử nghiệm cũng chỉ ra rằng nếu một gói dữ liệu mới đến trước khi quá trình tính toán của gói trước đó hoàn tất, hệ thống sẽ bỏ qua gói cũ để xử lý gói mới, đây là một đặc tính cần lưu ý khi thiết kế hệ thống tổng thể.

5.2. Phân tích khả năng phát hiện lỗi bit đơn và lỗi bệt burst error

Đây là phần đánh giá quan trọng nhất. Một kịch bản truyền 100 khối dữ liệu, mỗi khối dài 4016 bit (bao gồm CRC) đã được thực hiện. Trong mỗi khối, một số lượng bit lỗi nhất định (từ 2 đến 6 bit) được chèn vào ngẫu nhiên. Kết quả cho thấy: bộ giải mã CRC-16 phát hiện được 100% các khối có 2, 3 và 5 bit lỗi. Tuy nhiên, với các khối có 4 và 6 bit lỗi, bộ giải mã phát hiện được 99/100 khối. Trường hợp bỏ sót lỗi xảy ra khi mẫu lỗi (đa thức lỗi E(x)) tình cờ chia hết cho đa thức sinh G(x). Mặc dù xác suất này rất thấp, nó cho thấy không có cơ chế phát hiện lỗi nào là hoàn hảo tuyệt đối. Dù vậy, tỷ lệ phát hiện lỗi cực cao đã chứng minh sức mạnh của mã CRC trong việc bảo vệ tính toàn vẹn dữ liệu.

VI. Tương Lai Của Mã Hóa Kênh FPGA Hướng Phát Triển Tiềm Năng

Nghiên cứu về thiết kế và thi công bộ mã hóa CRC-16 trên nền tảng FPGA đã đạt được những kết quả đáng khích lệ, xây dựng thành công một giải pháp phần cứng hiệu quả để tăng cường độ tin cậy thông tin. Thành công này không chỉ là một tài liệu tham khảo giá trị cho lĩnh vực thiết kế vi mạch số mà còn mở ra nhiều hướng phát triển mới. Tương lai của Mã Hóa Kênh FPGA nằm ở việc tích hợp các thuật toán phức tạp hơn, không chỉ phát hiện lỗi mà còn có khả năng sửa lỗi (Forward Error Correction - FEC) như mã Hamming, Reed-Solomon hay LDPC. Việc kết hợp sức mạnh xử lý của FPGA với các thuật toán sửa lỗi tiên tiến sẽ tạo ra những hệ thống truyền thông cực kỳ bền bỉ và hiệu quả. Hơn nữa, các thiết kế có thể được tối ưu hóa hơn nữa về mặt tài nguyên sử dụng và mức tiêu thụ năng lượng, phù hợp cho các thiết bị IoT và hệ thống nhúng thế hệ mới, nơi hiệu suất và năng lượng là những yếu tố then chốt.

6.1. Tổng kết những đóng góp chính của công trình nghiên cứu

Công trình nghiên cứu đã đóng góp đáng kể vào lĩnh vực ứng dụng FPGA trong viễn thông. Thứ nhất, nó đã hiện thực hóa thành công thuật toán CRC-16 từ lý thuyết sang một sản phẩm phần cứng hoạt động được, với thiết kế chi tiết bằng Verilog HDL. Thứ hai, nghiên cứu đã thực hiện đánh giá hiệu năng một cách toàn diện trên cả phần mềm mô phỏng Xilinx ISE và kit FPGA thực tế. Các kết quả đánh giá khả năng phát hiện lỗi với các kịch bản thực tế đã cung cấp những số liệu định lượng quý giá. Cuối cùng, công trình này có giá trị như một tài liệu tham khảo học thuật và hướng dẫn thực hành cho sinh viên và kỹ sư trong ngành Điện tử - Viễn thông, đặc biệt là trong các môn học về thiết kế hệ thống số và vi mạch.

6.2. Triển vọng ứng dụng và các cải tiến tiềm năng trong tương lai

Triển vọng ứng dụng của bộ mã hóa CRC-16 trên FPGA là rất lớn. Nó có thể được tích hợp vào các hệ thống truyền thông công nghiệp sử dụng Modbus, các thiết bị ngoại vi máy tính theo chuẩn USB, hệ thống lưu trữ mạng (NAS), và nhiều hệ thống nhúng khác. Hướng phát triển trong tương lai có thể tập trung vào việc tạo ra một thiết kế có khả năng cấu hình linh hoạt, cho phép thay đổi đa thức sinh và độ dài khối dữ liệu một cách động. Một cải tiến khác là tối ưu hóa kiến trúc để giảm tài nguyên logic và tăng tốc độ xử lý, cho phép đáp ứng các giao thức truyền thông thế hệ mới với băng thông cao hơn. Ngoài ra, việc nghiên cứu kết hợp mã CRC với các kỹ thuật sửa lỗi khác trên cùng một chip FPGA sẽ tạo ra một giải pháp kiểm soát lỗi toàn diện và mạnh mẽ hơn.

22/09/2025

Trích đoạn nội dung tài liệu

CHƯƠNG 1: CƠ SỞ LÝ THUYẾT 1.1 Tổng quan về mã khối 1.1 Mã khối Mã khối là mã gồm k bit thông tin, người ta sẽ tính toán và tạo ra r bit kiểm tra tạo thành một từ mã (n, k) với n là tổng số bit (n = k + r). Nếu k bit được truyền từ bên phát qua môi trường đến bên thu. Nếu bên thu nhận được k bit nguyên vẹn thì sẽ tính ra được r bit giống bit kiểm tra đi kèm. Có một tham số được quan tâm là R = k/n được gọi là tỉ lệ thông tin chứa dữ liệu có ích trên tổng số thông tin truyền, tỉ lệ này liên quan mật thiết đến tốc độ truyền dữ liệu: ở điều kiện kênh truyền tốt thì ta cho tỉ lệ này cao lên, điều chế bậc cao hơn để cho tăng tốc độ, ngược lại trong điều kiện kênh truyền xấu thì phải cho tỉ lệ này thấp, bit kiểm tra nhiều lên và loại điều chế mang ít thông tin, bảo đảm độ tin cậy dữ liệu.

Với k bits ta có thể tạo ra 1 bộ dữ liệu gồm 2k thông tin, tương tự với n bits ta có 2n từ mã. Bởi vì n > k cho nên số lượng từ mã luôn luôn lớn hơn số lượng thông tin, suy ra rằng: sẽ có (2n – 2k) từ mã sẽ không phù hợp với bất kì thông tin nào, các từ mã này được gọi là từ mã không hợp lệ. Ví dụ: Mã Hamming (7, 4) với độ dài từ mã là n = 7 bit, có 3 bit mang dữ liệu và 7 bit chẵn lẻ. Khoảng cách Hamming Khoảng cách Hamming giữa hai dãy ký tự có chiều dài bằng nhau được định nghĩa là tổng số lượng các bit ở vị trí tương đương có giá trị khác nhau.

Khoảng cách Hamming dùng để đo số lượng thay thế cần phải có để đổi giá trị của một dãy ký tự sang một dãy ký tự khác. Ví dụ: Khoảng cách Hamming giữa hai từ x và y, kí hiệu là d(x, y). Từ x 0 0 0 Khoảng cách Hamming d(000,011) = 2 Từ y 0 1 1 Từ x 1 0 1 0 1 Khoảng cách Hamming d(10101,11110) = 3 Từ y 1 1 1 1 0 Các lỗi xảy ra trong quá trình truyền và khoảng cách Hamming có mối liên hệ với nhau: khoảng cách Hamming giữa từ mã nhận được và từ mã được gửi đi là số bit bị hỏng trong quá trình truyền. 3 Ví dụ: Trong ví dụ bên dưới từ mã có 2 lỗi và khoảng cách Hamming giữa 2 từ mã là d(11111, 01101) = 2.

Khoảng cách tối thiểu Khoảng cách tối thiểu là khoảng cách Hamming nhỏ nhất giữa tất cả các cặp ký tự có thể có trong một tập hợp các ký tự.1: Minh họa bộ mã (5,2). Datawords Codewords 00 00000 01 01011 10 10101 11 11110 Các cặp khoảng cách Hamming: d (00000, 01011) = 3 d (00000, 10101) = 3 d (00000, 11110) = 4 d (01011, 10101) = 4 d (01011, 11110) = 3 d (10101, 11110) = 3 Khoảng cách tối thiểu dmin = 3. Bằng cách xác định khoảng cách tối thiểu của bộ mã từ đó sẽ cung cấp cho chúng ta khả năng phát hiện lỗi ngẫu nhiên của bộ mã. Từ mã nhận được là tổng (phép cộng modulo-2) của từ mã được truyền và mẫu lỗi.

Vì vậy, lỗi có thể phát hiện được khi chúng không bị thay đổi từ từ mã được truyền thành từ mã hợp lệ khác hoặc bị thay đổi thành từ mã không hợp lệ. Theo định nghĩa của khoảng cách tối thiểu, hai từ mã bất kỳ của cùng một bộ mã khác nhau ít nhất là dmin bit. Trường hợp luôn đáp ứng điều kiện này là số lỗi nhỏ hơn khoảng cách tối thiểu dmin vì từ mã được truyền đi trong trường hợp này sẽ không bị biến thành từ mã hợp lệ khác. Do đó, có thể phát hiện đến t lỗi: t  d min  1 (1.1) 4 Bên cạnh đó, khoảng cách tối thiểu còn có mối quan hệ với khả năng sửa lỗi ngẫu nhiên theo biểu thức sau đây d min  1 w (1.2) 2 Với w là khả năng sửa lỗi ngẫu nhiên của mã.

Trong ví dụ trên w = 1, mã này có khả năng sửa được lỗi 1 bit. Từ hai biểu thức (1.2) có kết luận: bất kì mã nào có khả năng phát hiện được tất cả lỗi đôi thì có khả năng sửa được lỗi 1 bit.2: Các mô hình mã hóa kênh truyền. ARQ FECC Dừng Mã & ARQ liên tục Mã khối chập đợi Mã Go- Selective không back- Mã tuyến tính repeat tuyến N tính Mã không Mã tuần hoàn tuần hoàn Golay BCH Reed- Binary BCH Solomon e Hamming > (e = 1) 1 Trong thực tế, luôn luôn tồn tại nhiễu và các yếu tố khác can thiệp làm thay đổi thông tin mà chúng ta muốn gửi đi. Việc mã hóa dữ liệu sẽ giúp cho chúng ta có khả năng kiểm soát lỗi (Error control) từ đó cải thiện hiệu suất của hệ thống.

Có 2 loại kiểm soát lỗi đó là: 5 + Forward error control: thông tin sửa sai được thêm vào các ký tự hoặc các frame truyền đi, để bên nhận có thể phát hiện khi nào có lỗi và lỗi nằm ở đâu để sửa (có khả năng sửa lỗi). Cơ chế yêu cầu truyền lại ký tự/frame sai được dùng trong trường hợp này (Automatic Repeat Request – ARQ).2 Mã Hamming Là một mã cao cấp hơn của các mã kiểm tra chẵn lẻ đơn thuần. Mã Hamming chia dữ liệu thành các khối để tính các bit chẵn lẻ. Lấy ví dụ chúng ta có một từ dữ liệu dài 7 bit với giá trị là 0110101.

Đầu tiên, các bit của dữ liệu được đặt vào vị trí tương thích của chúng, sau đó các bit chẵn lẻ cho mỗi trường hợp được tính toán dùng quy luật bit chẵn lẻ số chẵn.3: Ví dụ mã hóa của mã Hamming (7,4). Thứ tự bit 1 2 3 4 5 6 7 8 9 10 11 Vị trí bit chẵn lẻ và các bit dữ liệu p1 p2 p1 p3 p2 p3 p4 p4 p5 p6 p7 Nhóm dữ liệu (không parity) 0 1 1 0 1 0 1 p1 1 0 1 0 1 1 p2 0 0 1 0 0 1 p3 0 1 1 0 p4 0 1 0 1 Nhóm dữ liệu (có parity) 1 0 0 0 1 1 0 0 1 0 1 Trong Bảng 1.3, bit parity p1 được tính cho các bit dữ liệu (d1d2d4d5d7), tương tự cho p2, p3 và p4. Bằng phương pháp này, các bit chẵn lẻ của từng nhóm dữ liệu sẽ kết hợp với nhau và tìm ra chính xác vị trí bit bị sai. Giả sử bit cuối cùng trong nhóm dữ liệu là d7 bị sai từ 1  0.

Nhóm dữ liệu mới sẽ là 10001100100.4 chúng ta sẽ phân tích quy luật giải mã của mã Hamming. Trong đó, vị trí bit bị sai là 1011 (đọc từ dưới lên) tương ứng với giá trị thập phân là 11.4: Ví dụ giải mã và sửa lỗi của mã Hamming (7,4). Thứ tự bit 1 2 3 4 5 6 7 8 9 10 11 Vị trí bit chẵn lẻ Kiểm tra Bit p1 p2 p1 p3 p2 p3 p4 p4 p5 p6 p7 và các bit dữ liệu chẵn lẻ chẵn lẻ Nhóm dữ liệu 1 0 0 0 1 1 0 0 1 0 0 1 nhận được p1 1 0 1 0 1 0 Sai 1 p2 0 0 1 0 0 0 Sai 1 p3 0 1 1 0 Đúng 0 p4 0 1 0 0 Sai 1 Hamming (7,4) có thể sửa bất cứ một bit lỗi nào và phát hiện tất cả lỗi của 1, 2 bit.2 Mã CRC Để đảm bảo phát hiện được lỗi hiện trong truyền thông nên cơ chế mã kiểm tra CRC được ứng dụng trong các giao thức như USB, CAN, Bluetooth… CRC được sử dụng làm cờ thông báo dữ liệu bị hỏng và ngăn không cho nó được gửi qua bus. Với việc các giao thức ngày nay thường hỗ trợ băng thông và tốc độ cao hơn, CRC là yếu tố cơ bản để giữ cho dữ liệu sạch và toàn vẹn trong một hệ thống nhúng.

CRC là một phương pháp phát hiện lỗi bằng cách gắn thêm một khối bit phía sau khối dữ liệu. Các bit bổ sung thêm vào được gọi là các bit CRC: giá trị chuỗi bit kiểm tra hay chuỗi CRC là số dư của phép chia chuỗi bit thông tin (message) cho một chuỗi bit đa thức sinh. Đa thức sinh sẽ khác nhau tùy theo các giao thức quy định. Phép chia trong tính toán CRC sử dụng phép modulo-2.

CRC rất phổ biến, vì nó rất đơn giản để lắp đặt trong các máy tính sử dụng hệ cơ số nhị phân, hiệu quả trong việc kiểm tra, và rất phù hợp để dò ra các lỗi gây ra bởi nhiễu trong khi truyền dữ liệu.  Các hàm CRC thường dùng và được chuẩn hóa Các mã kiểm tra CRC được chia thành nhiều tiêu chuẩn, mỗi ứng dụng khác nhau sẽ có các mã CRC phù hợp.5: Một số đa thức sinh g(x) thông dụng của mã CRC. Tên mã Ứng dụng Đa thức biểu diễn CRC-1 Bit chẵn lẻ x+1 7 CRC-5-EPC RFID x5 + x 3 + 1 CRC-8-WCDMA Mạng di động x8 + x7 + x4 + x3 + x + 1 Mạng điều khiển cục CRC-15-CAN x15 + x14 + x10 + x8 + x7 + x4 + x3 + 1 bộ USB, Modbus, ANSI, CRC-16-ANSI x16 + x15 + x2 + 1 X3.25, HDLC, CRC-16-CCITT x16 + x12 + x5 + 1 Bluetooth… Điện thoại không dây CRC-16-DECT x16 + x10 + x8 + x7 + x3 + 1 (cordless) x32 + x26 + x23 + x22 + CRC-32-IEEE Ethernet, Wifi, x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1 Phần thiết kế sẽ được tiến hành với mã CRC-16-ANSI trong Bảng 1. Bên gửi Bên nhận Bộ mã hóa Bộ giải mã a3 a 2 a 1 a0 a 3 a 2 a1 a0 0 0 0 Loại bỏ Decision logic Thương a3 a2 a1 Số chia Generator d 3 d 2 d1 d 0 Checker Kênh truyền a3 a 2 a 1 a0 r2 r1 r0 b3 b 2 b1 b0 q 2 q1 q0 Từ mã Từ mã Hình 1.1: Bộ mã hóa và bộ giải mã CRC.

Bộ tạo mã CRC Trong mô hình mã hóa ở Hình 1.1, chuỗi bit dữ liệu gồm k bits (ở hình minh họa là 4 bit a3a2a1a0) và từ mã phát đi gồm n bit nhị phân (ở hình minh họa là 7 bit: a3a2a1a0r2r1r0). Kích thước của chuỗi dữ liệu được nối thêm vào n - k bits số 0 (trong hình minh họa n – k = 7 – 4 = 3 bits) phía trước chuỗi dữ liệu. Tiếp theo, chuỗi dữ liệu 8 sau khi đã chèn thêm các bit 0 sẽ đi qua bộ tạo mã CRC (generator).

Nội dung được bảo vệ bản quyền — Tải xuống đầy đủ