Chương 1: Tổng quan. Chương này sẽ trình bày các thông tin tổng quát của đồ án. Chương 2: Cơ sở lý thuyết. Chương này sẽ trình bày toàn bộ các lý thuyết về trường hữu hạn, mã vòng và kỹ thuật mã hoá Reed Solomon.
Chương 3: Thiết kế và thi công. 11 Chương này sẽ trình bày chi tiết các giai đoạn thiết kế và thi công nên bộ mã hoá và giải mã Reed Solomon. Chương 4: Đánh giá và mô phỏng. Chương trình sẽ trình bày các kết quả thu được sau khi tổng hợp các thiết kế ở chương 3 và mô phỏng đánh giá chức năng mã hoá của thiết kế.
Chương 5: Kết luận và hướng phát triển. Chương này sẽ trình bày kết quả nghiên cứu và hướng phát triển tiếp theo của đồ án.5 Phạm vi của đề tài Trong đề tài này, nhóm chỉ tiến hành công đoạn thiết kế, thi công mã sửa lỗi Reed Solomon trên phần mềm Xiline ISE, chạy mô phỏng với các xác suất lỗi cho trước và có công đoạn đánh giá hiệu năng trên Matlab. Các kết quả mô phỏng, đánh giá được trình bày trong báo cáo đồ án là kết quả lý thuyết được tổng hợp từ phần mềm Xiline ISE Suite 14. 12 CHƯƠNG 2: CƠ SƠ LÝ THUYẾT 2.1 Hệ thống truyền thông kỹ thuật số Khái niệm hệ thống thông tin liên lạc là gồm tất cả các hệ thống và thiết bị đều tham gia vào quá trình truyền tải thông tin.
Hệ thống thông tin liên lạc được chia thành hai loại và dựa trên các loại tín hiệu khác nhau được truyền đi. Một là hệ thống thông tin liên lạc kỹ thuật số, hai là hệ thống thông tin liên lạc tương tự [6]. Những ưu điểm mà hệ thống thông tin liên lạc có thể đạt được là kiểm soát lỗi và mã hóa thông tin. Ngày nay hệ thống thông tin liên lạc kỹ thuật số thường được sử dụng rộng rãi như là hệ thống truyền hình, hệ thống điện thoại, hệ thống vô tuyến, hệ thống radar và hệ thống định vị.
Các hệ thống trên hầu hết có các nguyên tắc cơ bản giống nhau mặc dù các thuộc tính và chức năng của chúng khác nhau. Thông qua việc nghiên cứu về các đặc điểm chung của tất cả các hệ thống thông tin liên lạc, Mô hình chung của hệ thống thông tin liên lạc được thể hiện như hình 2.1: Sơ đồ khối quá trình truyền nhận dữ liệu trong viễn thông Bộ mã hóa (Encoder): Có chức năng thực hiện mã hóa. Bộ mã hóa bao gồm bộ mã hóa nguồn và bộ mã hóa kênh. Bộ điều chế (Modulator): Có nhiệm vụ chuyển đổi các tín hiệu đầu ra từ bộ mã hóa thành một định dạng có thể được truyền trên kênh và điều chỉnh tần số, biên độ hoặc pha của nó để thích ứng chuyển đường dài.
Kênh truyền (Channel): Có nhiệm vụ là phương tiện truyền thông qua đó hệ thống liên lạc truyền tín hiệu từ đầu gửi đến đầu nhận, hay đơn giản là đường truyền tín hiệu. Các loại kênh phổ biến bao gồm dây, cáp quang, cáp, truyền dẫn vô tuyến không gian, kênh vi ba. Có hiện tượng nhiễu hoặc nhiễu trong các kênh. 13 Nguồn gây nhiễu (Interference source): Sự can thiệp xảy ra trên đường truyền kênh hoặc phương tiện lưu trữ.
Bộ giải điều chế (Demodulator): Thực hiện giải điều chế các tín hiệu nhận được từ kênh. Giải điều chế là quá trình điều chế nghịch đảo. Bộ giải mã (Decoder): Giải mã các tín hiệu từ bộ giải điều chế và có quá trình ngược lại của mã hóa. Có hai loại giải mã: giải mã kênh và giải mã nguồn.
Kênh giải mã thực hiện phát hiện và sửa lỗi theo dự phòng được thêm vào phần mã hóa kênh. Giải mã nguồn làm giảm sự dư thừa do mã hóa kênh để chuyển từ mã thành thông tin ban đầu.2 Tổng quan về trường Galois Field 2.1 Khái niệm Field Fields là một dạng cấu trúc đại số trong đó một trường là một tập hợp mà phép cộng, trừ, nhân và chia được xác định và hoạt động như các phép toán tương ứng trên số hữu tỉ và số thực [7]. Về mặt hình thức, một field là một tập cùng với hai phép toán nhị phân trên được gọi là phép cộng và phép nhân. Phép toán nhị phân trên là một ánh xạ × → nghĩa là một phép tương ứng kết hợp với mỗi cặp phần tử có thứ tự của một phần tử được xác định duy nhất của.
Kết quả của phép tính cộng và gọi là tổng của và và được ký hiệu toán học là +. Tương tự, kết quả của phép tính nhân và được gọi là tích của và và được ký hiệu toán học là hoặc ⋅. Các phép toán này được yêu cầu để thỏa mãn các thuộc tính sau với , và là các phần tử tùy ý của trường .2 Trường Galois Trường Galois là một thành phần của trường hữu hạn Field. Khi mọi phần tử của trường hữu hạn đều có dạng trong đó p là số nguyên tố và n là số nguyên ( ≥ 1).
Ngược lại, với mọi số dạng thì tồn tại một trường có kích thước bao gồm mọi số dạng. Kí hiệu của trường Galois Field là ( ) [7]. Sử dụng các phép tính toán sẽ vô cùng phức tạp khi đang biểu diễn theo trường Galois Field là ( ).vì các quy luật số học sẽ không được áp dụng, tuy nhiên việc biểu diễn các phần tử dưới dạng đa thức sẽ giúp đơn giản hoá quá trình tính toán. Một đa thức được biểu diễn trên trường ( ) như sau: ( )= + + +⋯+ với ∈ ( ), = 0,1,2, … , (2.1) Một đa thức ( ) được gọi là tối giản khi và chỉ khi ( ) không thể biểu diễn là một tích của hai đa thức có bậc nhỏ hơn.3 Phép tính và thuộc tính Các phép tính và thuộc tính chính của trường hữu hạn Galois là: • Tất cả các phần tử của GF được xác định bởi các phép toán: cộng, nhân, chia và đảo.
• Kết quả của các phép tính trên bởi hai phần tử từ trường Galois phải là một phần tử trong trường Galois. • Tồn tại các phép tính +0= và ∗1 = cho bất kỳ phần tử A trong trường Galois. • Đối với mọi phần tử A trong trường Galois, phải tồn tại một phần tử nghịch đảo B sao cho + = 0 và ∗ = 1. Từ đó xác định phép nghịch đảo trong trường Galois.
• Cả hai phép toán cộng và nhân phải thỏa mãn tính chất giao hoán, liên kết và phân phối.3 Tổng quan về kỹ thuật mã hóa 2.1 Kỹ thuật mã hóa Mã hóa là việc thực hiện chuyển đổi các tín hiệu của một tập tín hiệu này thành một tập tín hiệu khác, với mục đích lưu trữ và trao đổi thông tin, việc thay đổi các cấu trúc thông tin tại nơi phát với mong muốn nhận được thông tin ở nơi thu chính xác hơn, có độ tin cậy, khả năng chống nhiễu cao hơn [8]. Ví dụ như tập hợp các số {0,1,2, …. Có 3 loại hình thức mã hóa đó là: Mã hóa nguồn : mục đích là biến đổi một tập tín hiệu gốc thành một tập đại lượng gốc nhưng khác chỉ số như số lượng bit, cách biểu diễn tập tín hiệu khác để dễ dàng lưu trữ và bảo mật. Mã hóa kênh : là cách biến đổi trên tập tín hiệu nguồn bằng một thuật toán nhằm giúp cho việc kiểm tra và sửa lỗi trong quá trình truyền.
Mã hóa đường truyền : là cách chuyển đổi tập tín hiệu thành các tín hiệu điện hoặc sóng vô tuyến để tiện lợi cho việc thực hiện truyền dẫn thông tin.2 Ứng dụng của kỹ thuật mã hóa Mã hóa nguồn : mã hóa ASCII dùng để mô tả sự vật dưới dạng văn bản để con người có thể hiểu được hoặc mã hóa Shanon-Fano và Lempe-Zib dùng để nén dữ liệu. Mã hóa kênh : như mã Hamming, mã vòng, BCH, Maximal-Lengths, LDPC, Reed-Solomon, …. Mã hóa đường truyền : Mã unipolar, polar, Bipolar… 2.4 Tổng quan về mã vòng Mã vòng là một loại mã khối tuyến tính, với ưu điểm là dễ dàng thực hiện bằng việc sử dụng logic tuần tự hoặc thanh ghi dịch chuyển. Một mã vòng có phần tử là = ( , , ,…, ) và có thứ hạng là số dịch chuyển phần tử còn được gọi là mã dịch vòng, được ký hiệu như sau: () =( , , ,…, , , ,…, ) (2.2) 16 Do là một loại của mã khối tuyến tính nên mã dịch vòng được thừa hưởng các tính chất của mã khối tuyến tính như thêm vào các bit thông điệp một số lượng nhất định các bit kiểm tra để đảm bảo tính toàn vẹn của thông diệp sau khi nhận tại máy phát.
Các mã vòng được kí hiệu ( , ) với n là chiều dài khối từ mã và là số lượng khối từ mã chứa thông điệp, một số mã vòng phổ biến như mã Reed–Muller, mã Hamming, mã Goppa, mã Golay hay mã Reed-Solomon [9]. Một từ mã vòng có thể được biểu diễn dưới dạng hàm đa thức ( ), với hệ số được xác định theo (2 ) trong đó là một số nguyên tương ứng đến vị trí của hệ số, là một vectơ mã, biểu diễn đa thức cho vectơ mã là ( ) như sau: ( )= + +⋯+ (2.3) Tương tự như mã vòng, mã dịch vòng được biệu diễn đa thức như sau: ( )( )= + +⋯+ (2.4) Mặc khác trên trường GF(2) chúng ta có: () ( ) = ( )( + 1) + ( ) (2.6) Trong số các đa thức mã của một mã vòng đã cho ( , ) sẽ có một đa thức bậc nhỏ nhất r với = − và được gọi là đa thức sinh Generator polynomial, có hệ số = = 1 và được biểu diễn như sau: ( )= + + ⋯+ (2.1 Trình bày một mã vòng (7, 4) với ( ) = 1 + + .1: Mã vòng C(7, 4) Thông điệp Từ mã Đa thức mã = ⋯ = ⋯ ( )= + +⋯+ 0000 0000000 0 1000 1101000 1+ + 0100 0110100 + + 1100 1011100 1+ + + 0010 0011010 + + 1010 1110010 1+ + + 17 0110 0101110 + + + 1110 1000110 1+ + 0001 0001101 + + 1001 1100101 1+ + + 0101 0111001 + + + 1101 1010001 1+ + 0011 0010111 + + + 1011 1111111 1+ + + + + + () () Từ ví dụ trên ta có mối liên hệ giữa và ( ) theo bảng 2.