Thứ Hai, 26 tháng 8, 2013

Tìm hiểu về Forward Error Correction - FEC (sửa lỗi trước)

Forward Error Correction là một kỹ thuật được áp dụng cho việc truyền dữ liệu mà chủ yếu là cho lĩng vực multicast (một phát cho tất cả). FEC là kỹ thuật sữa lỗi, trong đó các lỗi xảy ra có thể được sữa bởi FEC khi dữ liệu đến đầu nhận. Khả năng sữa lỗi của FEC là tùy thuộc vào mã được sử dụng để mã hoá. Forward là do khi áp dụng mã FEC vào thì đầu nhận có khả năng sữa lỗi rồi nên không cần Auto Retransmit reQuest (ARQ), do vậy mà các dữ liệu được gửi đến một cách liên lục.
Thực ra FEC là một kỹ thuật cũ, 1986 người Mỹ lần đầu áp dụng FEC vào trong truyền thông tin giữa tàu Voyager và trạm mặt đất, 1995s thì được đưa vào trong truyền thông cáp quang. Còn đầu những năm 1990s thì nó đã được đưa vào DVB rồi. Nhưng mình đã tìm bằng google tất cả những site Việt Nam rồi nhưng không có site nào nói về FEC cả.

tiếp theo là hoạt động của FEC. FEC kh6ng thường đi một mình mà thường đi với Bit Interleave Pairyty -x, scrambler hay với một mã khác. đầu tiên là các dữ liệu sẽ được dóng vào một khung dữ liệu khung này là tuỳ vào ứng dụng và tuỳ loại mã được dùng.
Lấy ví dụ là cáp quang nha.
Một khung cáp quang là khác nhau giữa những chuẩn như SONET , và STM nhưng theo ITU đền nghị là xài khung OTU của họ là một khung dữ liệu có 3 phần:
-Overhead : 16 byte cung cấp những thông tin về payload và các thông tin khác .
-payload đay là phần dữ liệu. từ byte 17 đến 3824
-phần còn lại là FEC.
Trong khung OTU thì độ dài là cố định ,chuân là 4080 byte. Những chỗ vào không dùng thì được chèn toàn là "0".
Tôi chọn mã RS(255,239), khả năng sữa lỗi là (255-239)/2=8 byte. mã này được tạo ra từ lý thyết trường Galois Field, hay còn gọi là trường hữu hạn. Theo lý thuyết thì GF(2^m) với m là bậc cao nhất của đa thức nguyên (gốc).Do 255 ứng với 2^8 nên một word mà RS quản lý là 8 bit. vậy là trường này có 256 phần tử và mổi phần tử được tính bằng tổn của các phần tử khác trong trường .VD : x1=00000001 thì x3 =x1+x2=00000011. Trong hầu hết các ứng dụng dùng RS(255,239) thì đa thức nguyên đượ chọn làp(X)=1+x1+x2+x4+x8 (?) mã của bất kỳ một phần tử nào là dư số của nó trong phép chia của nó cho da thức nguyên.VD: x9---->x9/p(X).
cứ như thế cho các phần tử khác. phần RS này khá dài nên chỉ trình bày sơ thôi. 
Điều khó khăn của RS là mã hoá cực dễ,chỉ cần vài bộ shift là xong. Nhưng để giải mã nó thì phải dùng 4 thuật toán mà 80% dân điện tử chưa bao giờ nghe :
Đầu tiên là Symdrom để xác định xem dữ liệu nhận được có bị lỗi không ?Sau đó là thuật tóan Euclidean để tìm vị trí lỗi và số lượng lỗi, sau đó là thuật toán Forney. Cuối cùng là sữa lỗi.
Còn rất rất dài và rất nhiều công thứ mà mình không đưa lên được nhưng mình muốn các bạn biết tới nó và tiền kiếm được từ nó.
các dịch vụ truyền hình số của Việt Nam không có cái đầu giải mã nào mà được lập trình giả mã bởi người việt cả, tất cả là mua về rồi ráp. trong khi đó tụi nó lập trìng trên FPGAASICs từ khuya rồi bán cho mình. Nhưng lập trìng trên DSP thì dễ hơn.
Các bạn cứ thử search trên mạng sẽ thấy là đây mới là tương lai 5 năm của ngành viễn thông.


Mã hóa là một trong lĩnh vực khó gặm nhất trong viễn thông. Nó là thành phần không thể thiếu được trong hệ thống viễn thông, mục đich của mã hóa là tăng độ tin cậy của thông tin khi truyền qua các kênh thông tin hoặc trong thiết bị lưu trữ. Tăng độ tin cậy của kênh thông tin cũng đồng nghĩa với việc giảm năng lượng phát mà không làm giảm chất lượng của kênh thông tin.

Mình có một số bổ sung cho scoopydoo. Trước tiên là FEC, FEC là một khái niệm chung để chỉ phương thức phát hiện và sửa lỗi ở phía nhận. Để thực hiện FEC, ta cần có một bộ mã có khả năng phát hiện và sửa lỗi ví dụ như Reed Solomon code, Hamming code, Fire code... Dữ liệu cần truyền được mã hoá trước khi truyền, tại phía nhận, bộ thu sẽ giải mã và xác định xem có lỗi xảy ra không và sửa lỗi nếu có thể.
Còn về mã Reed Solomon, đây cũng là một mã thuộc lớp mã vòng (Cyclic code). Do đó việc mã hóa rất đơn giản là tạo ra các parity, có thể thực hiện việc này bằng các chia đa thức hay nhân với ma trận sinh. Tuy nhiên việc giải mã Reed Solomon lại cực kỳ phức tạp do ta phải tính toán ra bao nhiêu lỗi trong từ mã và vị trí của lỗi đó.
Việc giải mã Reed Solomon phải qua 4 bước:
+ Xác định Syndrom, tương tự như mã CRC.
+ Dùng algebraic decoder để tín toán đa thức lỗi (error locator polynomial) (có thể dùng thuật toán Perterson hay Berlekam-Massey)
+ Xác định nghiệm của error locator polynomial bằng thuật toán Chien search (ông Chien này là người Trung Quốc, lúc đầu mình cứ tưởng là Việt Nam tự hào wá ) suy ra được số lỗi và vị trí của lỗi.
+ Dùng thuật toán Forney để xác định biên độ của lỗi ( nếu là mã nhị phân thì bỏ qua bước này vì biên độ lỗi chắc chắn là 1)
+ Cuối cùng chỉ việc lấy từ mã nhận được (có lỗi) trừ đi lỗi là xong.

Cái khó của mã Reed Solomon là ở chỗ hiểu được cấu trúc của nó bởi nó được xây dựng trên trường Galois GF(p) mà không phải ai cũng rành về lĩnh vực này. Tuy nhiên để lập trình được thì không phải là chuyện khó, vì tất cả các công thức, thuật toán đều rất rõ ràng.

0 nhận xét:

Đăng nhận xét