Mã xoắn Convolution Code

CHƯƠNG VI MÃ XOẮN CONVOLUTION CODE A.\Mã xoắn-mã tích chập Mã xoắn là mã được hình thành bằng cách đưa chuỗi bit cần mã hoá đi qua các thanh ghi dịch tuyến tính có số trạng thái nhất định.Các loại mã xoắn không phân biệt phần dữ liệu và phần dữ liệu mã hoá thêm vào như ở mã khối.Ngõ ra của mã xoắn là các bộ cộng modulo-2 của các thanh ghi dịch.Phần mã hoá thêm vào được phân phối đều khắp dữ liệu được mã hoá:các bit ngõ ra phụ thuộc vào các trạng thái của các thanh ghi và bit ngõ vào tương ứng tại thời điểm đó.Bộ mã hoá xoắn đơn giản dùng để giải thích ở đây có dạng: (Hình 6.1) Bộ mã hoá mã xoắn đơn giản nhất Mã xoắn thường được mô tả bởi 2 tham số là tỷ lệ mã hoá và chiều dài cưỡng bức-“constrain length”-.Tỷ lệ mã hoá của mã xoắn được định nghĩa như sau: r = với k là số bit dữ liệu ngõ vào tại một thời điểm và n số bit mã hoá ở ngõ ra ở một đơn vị thời gian tương ứng Với chuỗi bit tin L bit đưa vào bộ mã hoá xoắn 1/n và K=m+1 thì từ mã ngõ ra có chiều dài là n(L+m),nên tỷ lệ mã hoá sẽ là : r = bits/symbol Tuy nhiên trong thực tế,L >> m nên ta có : r bits/symbol Chiều dài cưỡng bức của mã xoắn là: với m là kích thước tối đa trong bất kỳ thanh ghi dịch nào dùng để lưu trữ trạng thái thông tin của bộ mã hoá xoắn.Chiều dài cưỡng bức còn được hiểu là số lần dịch chuyển của một bit để đi hết các thanh dịch.Chiều dài cưỡng bức quan hệ phụ thuộc đến số lượng bit ngõ ra. Khi k = 1,tức là bộ mã xoắn có r = 1/n được gọi là mã xoắn nhị phân-“binary convolution”.Ngược lại khi k 2 thì ta gọi đó là mã xoắn phi nhị phân-“nonbinary convolution”.Một mô hình mã xoắn phi nhị phân đơn giản khác là: Flip-flop bộ cộng modulo-2 (Hình 6.2) k = 2,n =3,r =2/3,K=2 Convolution encoder Mã xoắn hình 6.2 trên có chuỗi ngõ vào tại một thời điểm là 2 bit và chuỗi ngõ ra tương ứng là 3. Một bộ mã hoá xoắn có thể được miêu tả bằng nhiều cách khác nhau như dùng hàm sinh,biểu đồ cây,biểu đồ máy trạng thái và biểu đồ mắt cáo.Hàm đa thức sinh biểu diễn của mã xoắn hình 6.1 là g (1) = (1,1,1) và g (2) = (1,0,1) hoặc có thể viết như sau g(D) = 1+D+D và g(D) = 1+D.Đa thức sinh của một bộ mã hoá mã xoắn có thể xác định bằng cách cho chuỗi bit 10000… đi vào bộ mã hoá,khi đó chuỗi bit ngõ ra tại từng bộ cộng modulo-2 là đa thức sinh của mã xoắn đó.Bên cạnh đó,đa thức sinh của bộ mã hoá mã xoắn có thể xác định như sau:số phần tử của đa thức sinh của một ngõ ra bằng chiều dài cưỡng bức và giá trị của phần tử thứ i bằng “1” nếu thanh ghi dịch trạng thái thứ i nối với bộ cộng của ngõ ra đó.Ngược lại sẽ có giá trị là “0”.Dựa vào các đa thức sinh của một mã xoắn ta có thể biết được cấu tạo bộ mã hoá. Sơ đồ cây mô tả bộ mã hoá mã xoắn hình 6.1 có dạng như sau: 0 1 00 00 00 11 11 11 11 10 10 01 01 00 01 10 Sơ đồ cây mô tả bộ mã hoá mã xoắn hình 6.1 (Hình 6.3) Mã xoắn còn được gọi là mã mắt cáo-“Trellis code”- vì các mã xoắn có thể được mô tả bằng biểu đồ mắt cáo-“trellis diagram”. B.\Biểu đồ trellis - mắt cáo Trong các cách trên thì biểu đồ mắt cáo là phương tiện tiện lợi và hữu ích để mã hoá và giải mã một mã xoắn bởi tính dễ hiểu và trực quan nhất.Tiếp theo chúng ta sẽ tìm hiểu về biểu đồ này.Trong ví dụ trên có 2 bộ lưu trữ-“delay”- để tạo ra 4 trạng thái.Bộ delay bên trái được gán trọng số và bộ delay bên phải được gán trọng số .Với một trạng thái cho trước và một bit ngõ vào sẽ cho ra 1 trạng thái kế tiếp được lưu trữ trong các bộ delay. trạng thái hiện tại trạng thái kế,nếu trạng thái bit ngõ ra,nếu input=0 input=1 hiện tại input=0 input=1 00 00 10 00 00 11 01 00 10 01 11 00 10 01 11 10 10 01 11 01 11 11 01 10 Bảng chuyển đổi trạng thái (Hình 6.4) Bảng bit ngõ ra Biểu đồ mắt cáo là sự kế hợp giữa 2 bảng chuyển đổi trạng thái và bảng bit ngõ ra.Bốn trạng thái của biểu đồ được vẽ thành 4 hàng nút nằm ngang.Những nút bên trái của biểu đồ tượng trưng cho trạng thái hiện tại và những nút bên phải của biểu đồ tượng trưng cho trạng thái kế tiếp.Tại mỗi nút ở trạng thái hiện tại có 2 nhánh đến 2 nút ở trạng thái kế tiếp,nhánh trên là nhánh đại diện cho bit ngõ vào là 0,nhánh dưới là nhánh đại diện cho bit ngõ vào là 1.Và 2bit nhãn trên mỗi nhánh là đáp ứng bit ngõ ra tương ứng của mã xoắn. (Hình 6.5) Biểu đồ mắt cáo Để mã hoá 1 chuỗi dữ liệu ta sẽ mở rộng biểu đồ mắt cáo ra nhiều lần,số lần mở rộng của biểu đồ chính bằng số lượng bit cần mã hoá.Các nút của một cột đại diện cho các trạng thái tại cùng 1 thời điểm.Khi bắt đầu ta luôn bắt đầu tại time 0 và trạng thái 00.Chúng ta sẽ đi theo đường phụ thuộc vào bit ngõ vào:nếu bit ngõ vào là 0 thì ta đi theo nhánh trên và nếu bit ngõ vào là 1 thì ta đi theo nhánh thấp hơn.Và nhãn của từng nhánh là chuỗi bit ngõ ra tương ứng.Giả sử chuỗi bit ngõ vào là 1011,ta sẽ có chuỗi bit đáp ứng ngõ ra là 11 10 00 01. (Hình 6.6) Biểu đồ mắt cáo mã hoá chuỗi bit 1011 C.\Biểu đồ trạng thái: Dựa vào biểu đồ trellis ở hình 6.5 ta có thể dựng biểu đồ trạng thái của bộ mã hoá mã xoắn ở hình 6.1.Để thuận tiện trước tiên ta ký hiệu các trạng thái có thể có của bộ mã hoá đó như sau: Trạng thái Trạng thái a 00 b 10 c 01 d 11 bit vào là 0 bit vào là 1 (Hình 6.7) Biểu đồ trạng thái của bộ mã hoá mã xoắn hình 6.1 Biểu đồ trạng thái còn là một công cụ hữu ích để tìm tính chất khoảng cách và khảo sát tỷ lệ lỗi của một bộ mã hoá mã xoắn. D.\Giải mã mã xoắn-thuật toán Veterbi Thuật toán Viterbi được công bố vào năm 1967 bởi Viterbi.Sau đó Foney chỉ ra rằng đó là thuật toán gần nhất dùng để giải mã cho mã mắt cáo vào năm 1973.Thực tế là bộ giải mã sẽ chọn chuỗi với số metric nhỏ nhất so với chuỗi nhận được.Và thông tin sẽ được khôi phục dựa vào chuỗi mà bộ giải mã chọn,còn gọi là chuỗi đã sửa hoặc chuỗi ước lượng. Hình 6.8 dưới là mô hình biểu đồ khối của hệ thống mã xoắn.Chuỗi thông tin m sẽ được mã hoá thành chuỗi mã xoắn x.Chuỗi mã xoắn x sẽ được truyền trên kênh truyền không nhớ rời rạc có can nhiễu nên sẽ cho chuỗi ngõ ra của kênh truyền là y.Bộ giải mã Viterbi sẽ tính toán để chọn chuỗi ước lượng là x’,chuỗi x’ được ước lượng dựa trên chuỗi r.Thông tin dữ liệu m’sẽ được khôi phục dựa vào chuỗi x’. (Hình 6.8) Khái quát về hệ thống dùng mã xoắn Cơ sở của việc chọn chuỗi ước lượng được giải thích như sau: Với mô hình trên,để m’ = m khi và chỉ khi bộ giải mã ước lượng x’ = x.Ngược lại sẽ có giải mã sai tại bộ nhận.Xác suất ước lượng x’từ chuỗi bit y nhận được để m’ = m là lớn nhất nếu xác xuất lỗi của việc giải mã sai là nhỏ nhất .Có nghĩa là p(x’=x | y) là lớn nếu p(x’ x| y) là nhỏ nhất.Nói cách khác,nếu ta đặt p(y|x) là xác suất nhận được chuỗi y khi chuỗi phát là x thì bộ giải mã theo xác suất lớn nhất đối với kênh truyền không nhớ rời rạc được mô tả như sau:ước lượng chuỗi x’ với điều kiện ln p(y | x) là lớn nhất. Xét kênh truyền BSC: (Hình 6.9) Kênh truyền nhị phân đối xứng BSC Kênh truyền BSC là kênh truyền có các đặc điểm như sau:ngõ vào là chuỗi nhị phân,ngõ ra cũng là chuỗi nhị phân,n bit vào thì có n bit ở ngõ ra.Xác xuất truyền bit 0(hoặc 1) mà nhận được bit 1(hoặc 0) là p,được mô tả như sau: P( 0 | 1 ) = P (1 | 0) = p P(0 | 0) = P (1 | 1) = 1-p Nếu 2 chuỗi x,y là các chuỗi nhị phân có cùng chiều dài là N và 2 chuỗi có những bit khác nhau.Gọi xi ,yi là vị trí thứ i trong 2 chuỗi trên.Khi đó ta có: p(y | x) = Lấy logarit hệ số e cho 2 vế: ln p(y | x) = Do tính chất kênh truyền BSC ta có: p(y | x) = p nếu y x và p(y | x) =1- p nếu y= x Giả sử chuỗi y khác chuỗi x ở d vị trí.Số d đó sẽ được gọi là khoảng cách Hamming giữa 2 chuỗi là y và x.Vậy: ln p(y | x) = d ln( p )+(N-d)ln(1-p) = d ln() + N ln(1-p) Thường thì xác suất xuất hiện một lỗi là nhỏ,ta giả sử p<1/2.Khi đó N ln(1-p) là hằng số đối với mọi chuỗi x,nên việc giải mã theo xác xuất lớn nhất đối với kênh truyền BSC là:ước lượng chuỗi x’ có khoảng cách Hamming là nhỏ nhất giữa 2 chuỗi là x và y. Nhận định trên chỉ dành cho kênh truyền BSC.Đối với các bộ giải mã trên các kênh truyền khác chuỗi y sẽ được so sánh với mỗi chuỗi x có thể có của bên phát.Và 1 chuỗi “gần nhất” với y sẽ được chọn,chuỗi mà có số bit khác với chuỗi y là nhỏ nhất. Trong thuật toán giải mã Viterbi,chúng ta sử dụng khoảng cách Hamming giữa chuỗi nhận được và chuỗi chuỗi ngõ ra có thể của kênh truyền để tính d(y,x) ,được gọi là tính metric.Khoảng các Hamming được tính bằng cách đếm số bit khác nhau giữa 2 chuỗi.Metric của nhánh là khoảng cách Hamming mà được tính cho đường nối giữa 2 trạng thái trước đó và trạng thái hiện tại. Thuật toán Viterbi quyết định cứng có thể được khái quát như sau: 1.Giả sử bộ mã hoá của mã xoắn khởi đầu ở trạng thái 0.Đặt số metric bằng 0 và t cũng bằng 0 tại nút khởi đầu. 2.Tại mỗi nút t+1,tính tổng metric của trạng thái trước đó tại nút t và metric của nhánh nối đến nút đó.Tại mỗi trạng thái chọn đoạn đường có tổng số metric nhỏ nhất và ghi lại tổng số metric tại nút đó.Tiếp tục đi dến trạng thái kế. 3.Nếu chúng ta đến cuối biểu đồ thì ngừng lại rồi chọn con đường có số metric nhỏ nhất làm từ mã đã được giải mã.Ngược lại tăng t thêm 1 rồi trở về bước 2. Ví dụ: ta có chuỗi bit cần truyền là u = 1 0 1 0 1 0 0,thì chuỗi từ mã là v= 11 10 00 10 00 10 11 vì có nhiễu nên r= 11 11 00 10 00 10 11 xem như là chuỗi nhận được có bit lỗi được gạch dưới. (Hình 6.10) Biểu đồ trellis dùng để giải mã chuỗi bit nhận được Trước hết để áp dụng thuật toán Viterbi,ta mở rộng biểu đồ ra như trên.Tại mỗi nút được gán cho 1 cặp số:số đầu tiên đại diện cho trạng thái trước đó và số thứ hai đại diện cho tổng số metric tích luỹ được.Sau khi tính toán từ chuỗi biểu tượng nhận được ta tìm được con đường 00-10-01-10-01-10-01-00,con đường được tô đậm như hình là có số metric nhỏ nhất.Dựa vào con đường tìm được thì chuỗi ước lượng v’=11 10 00 10 00 10 11,là chuỗi được tạo ra từ chuỗi bit 1 0 1 0 1 0 0.Từ chuỗi ước lượng,bộ giải mã sẽ giải mã thành chuỗi bit u’=1 0 1 0 1 0 0,trùng khớp hoàn toàn với chuỗi dữ liệu đã truyền.Qua ví dụ này cho thấy thuật toán Viterbi dùng để giải mã có khả năng khôi phục được chuỗi dữ liệu gốc dù nhận được chuỗi không đúng. Thuận lợi lớn nhất của thuật toán giải mã Viterbi đối với một mã xoắn r=k/n,chiều dài cưỡng bức K là số lượng thao tác để giải mã chuỗi L bit là L2 E.\Hàm truyền của mã xoắn Hàm truyền của một mã xoắn phản ánh về tính chất khoảng cách và tỷ lệ lỗi của một mã xoắn.Để tìm hàm truyền của một mã xoắn ta sử dụng biểu đồ trạng thái của chính mã đó.Chúng ta sẽ sử dụng hình 6.7 để tìm hàm truyền cho mã xoắn r=1/2 và K=3 ở hình 6.1.Trước hết chúng ta sẽ thay đổi một chút về máy trạng thái của mã náy như sau:trạng thái toàn không-“all-zero state” a sẽ được phân làm trạng thái khởi đầu là a và trạng thái kết thúc là e.Và vòng lặp tại đây cũng được loại bỏ vì vòng lặp này có khoảng cách Hamming là 0 so với chuỗi mã toàn không.Và thay đổi chủ yếu tại hình dưới đây chính là cách đặt nhãn cho các nhánh.a b c e d DLI DL DL DLI DL DLI LI Bit vào là 0 Bit vào là 1 (Hình 6.11) Biểu đồ trạng thái được thay đổi D=1, D, D, D,… là cách khoảng cách Hamming(còn gọi là các trọng số) của nhánh đó so với nhánh ngõ ra toàn không.I là các trọng số Hamming ứng với bit ngõ vào;nên với ngõ vào là 0 chúng ta có I=1 và với ngõ vào là bit 1 thì I=I.Và L là chiều dài của nhánh và có giá trị hệ số mũ luôn bằng 1.Ví dụ xét đường abcbdce sẽ có nhãn là DLI.Có nghĩa là trọng số Hamming của từ mã ngõ ra bộ mã hoá sẽ là 7,chiều dài của đoạn đường của từ mã là 6 và trọng số Hamming của từ chuỗi bit ngõ vào là 3.Nếu chúng ta xem con đường cơ bản-“fundamental path”- là con đường bắt đầu tại a và kết thúc tại e.Xem Td,l,i là số đường cơ bản nối a với e được đặt nhãn là DLI thì ta có hàm truyền là tổng các con đường có thể có nối giữa 2 điểm a và e: T(D,L,I) =Td,l,I . DLI Bên cạnh đó ta có thể tính hàm truyền T(D,L,I) như sau: T(D,L,I)= Xe/Xa .Với Xi là biến tạm tại nút i và bằng tổng các nút nối đến i và nhãn của các nhánh là độ lợi.Nên: Xb = DLI. Xa + LI . Xc Xc = DL .Xb + DL . Xd Xd = DLI .Xb + DLI. Xd Xe = DL .Xc Giải phương trình T(D,L,I)= Xe/Xa ta sẽ có: T(D,L,I) = Triển khai (1-DLI(1+L)) ta có: T(D,L,I) = DLI + DLI(1+L)+ DLI(1+L)+… Dựa vào hàm truyền tìm được trên ta thấy: a.Không có đoạn đường cơ bản nào có khoảng cách Hamming là 0,1,2,3 hay 4 so với con đường ngõ ra toàn không. b.Có một đoạn đường duy nhất nối a và e mà có khoảng cách Hamming là 5,chiều dài là 3 và trọng số ngõ vào 1 bit đơn là 1 so với đoạn đường toàn không. c.Có 2 đoạn đường có cùng khoảng cách Hamming là 6.Một đoạn đi qua 4 nhánh và 1 đoạn đi qua 5 nhánh,nhưng cả 2 cùng có trọng số ngõ vào 2 so với con đường toàn không. d.Có 4 đoạn đường có cùng khoảng cách Hamming là 7.Một đoạn đường có chiều dài là 5;2 đoạn có chiều dài là 6 và 1 đoạn có chiều dài là 7.Cả 4 có cùng trọng số ngõ vào là 3. … Vậy dựa vào hàm truyền của mã xoắn ta biết được khoảng cách Hamming nhỏ nhất giữa bất kỳ con đường cơ bản nào với con đường toàn không.Trong trường hợp tính trên thì khoảng cách đó là 5.Khoảng cách đó gọi là khoảng cách tự do nhỏ nhất và ký hiệu là dfree hoặc df .Với mã xoắn có số bit lỗi của từ mã nhận được so với từ mã đã phát bé hơn ½ dfree thì bộ giải mã luôn giải mã đúng với mọi trường hợp.Ứng với dfree =5 thì số bit lỗi lớn nhất cho phép để bộ giải mã luôn giải mã đúng là 2. F.\Xác xuất lỗi của phương pháp giải mã quyết định cứng Với việc sử dụng thuật toán Viterbi cho việc giải mã mã xoắn trên kênh truyền BSC.Đặc điểm của thuật toán này là sử dụng các metric(khoảng cách Hamming) để ước lượng chuỗi bit đã phát và tại mỗi nốt của của biểu đồ mắt cáo luôn có 2 khả năng để chọn.Giả sử chuỗi phát là đoạn đường toàn không có chuỗi từ mã nhận được tại bên thu,giả sử chuỗi này so sánh với chuỗi mã ngõ ra toàn không ở một vài nút có khoảng cách Hamming là d.Nếu d lẻ và số bit lỗi d’của chuỗi nhận được bé hơn 1/2(d+1) thì bộ giải mã sẽ tìm lại đúng chuỗi đã phát là chuỗi ngõ vào toàn không.Ngược lại sẽ giải mã sai.Ta có xác suất giải mã sai là: P(d)= p(1-p) trong đó p là xác suất lỗi bit của kênh truyền BSC.Nếu d’=1/2d thì bộ giải mã sẽ tìm thấy 2 con đường có cùng số metric và sẽ chọn ngẫu nhiên 1 đường nên xác suất lỗi được xem là ½.Khi này xác suất lỗi sẽ là: P(d)= p(1-p) + ½ p(1-p) Tại một nút bất kỳ,có rất nhiều đoạn đường trở về trạng thái e.Ta có thể viết tổng quát như sau: Pe < với ad là số con đường có cùng khoảng cách là d.Đây là hệ số có thể xác định từ hàm truyền T(D,L,I). Mặc khác cận trên của xác xuất giải mã sai theo công thức như sau: P2(d)< [4p(1-p)] => Pe < ad [4p(1-p)] < T(D)| Vì tỷ lệ lỗi BER được dịnh nghĩa dựa trên số bit lỗi khi giải mã từng bit nên: (BER) Vậy đối với kênh truyền BSC: (BER) G.\Độ lợi mã của mã xoắn Xét kênh truyền BSC: Với kênh truyền này thì tham số Z được định nghĩa như sau: Z=2 Và xác suất truyền-“transition probability”-p được định nghĩa như xác suất lỗi của điều chế tín hiệu PSK: p=erfc() với E là năng lượng của từng symbol mã và N/2 là mật độ phổ công suất của tín hiệu nhiễu. erfc() exp(-) nên p có thể lấy xấp xỉ như sau: p 0.282 exp(-) (*) nếu không có sử dụng mã hoá thì BER=p đối với tín hiệu nhị phân PSK và vì p << 1,E/N lại lớn vậy nên giá trị Z xấp xỉ là: Z 1.06 exp (-) Đối với mã xoắn có tỷ lệ mã r,có nghĩa có r symbol mã khi mỗi bit tin đưa vào.Nên năng lượng của symbol mã liện hệ với năng lượng bit là: E = r.E => Z 1.06 exp (-) Thay thế Z vào biểu thức BER AZ có A=,ta sẽ có biểu thức sau: BER (1.06)Aexp(-) Khai triển vế phải công thức trên,giá trị của số hạng tổng phần lơn tập trung ở số hạng đầu tiên nên: BER (1.06) A exp(-) (**) Với mã xoắn như hình 6.1 mô tả ta cók =1, A=1.Khi so sánh hệ số mũ của (**) với hệ số mũ của công thức (*) thì hệ số mũ của BER có sử dụng mã hoá lớn hơn hệ số mũ của BER không có sử dụng mã một lượng là d.r/2.Có nghĩa BER của hệ thống có mã hoá sẽ nhỏ hơn BER của hệ thống không mã hoá.Nếu E/N là lớn và xác định,ta thấy giá trị BER bị chi phối bởi hệ số mũ.Tóm lại khi sử dụng thuật toán Viterbi quyết định cứng để giải mã xoắn ta có thể đạt được độ lợi mã theo công thức sau: Ga=10log (dB) (***) Với kênh truyền có nhiễu Gauss-“AWGN channel”- tham số Z được định nghĩa như sau: Z = exp Thực hiện lại các bước như đối với kênh truyền BSC,ta có xác suất lỗi BER là: BER (1.06) A exp(-) Và độ lợi mã là: Ga=10log(d.r) (dB) (****) Nếu so sánh công thức (****)với công thức (***) thì ta thấy độ lơi mã của kênh truyền ngõ vào nhị phân AWGN sẽ lớn hơn độ lợi mã của kênh truyền BSC khoảng 3db.Có nghĩa rằng máy phát của kênh truyền BSC phải thêm 3dB vào năng lượng(công suất) của tín hiệu cần truyền khi so với kênh truyền có ngõ vào nhị phân AWGN để đạt cùng mộ xác suất lỗi. Nhìn chung ta thấy xác xuất lỗi và độ lợi mã của một mã xoắn thì phụ thuộc vào hệ số khoảng cách d.Và hệ số này được dùng để đánh giá một mã xoắn: d càng lớn thì bộ mã xoắn đó càng ưu việt hơn.Với khoảng cách tự do càng lớn,đã có rất nhiều nỗ lực để tìm ra những bộ mã xoắn tốt. Bảng mô tả một số mã xoắn r=1/2 r=1/3 K Đa thức sinh d K Đa thức sinh d 3 5 7 5 3 5 7 7 8 4 15 17 6 4 13 15 17 10 5 23 35 8 5 25 33 37 12 6 53 75 8 6 47 53 75 13 7 133 171 10 7 133 145 175 15 8 247 371 11 8 225 331 367 16 9 561 753 12 9 557 663 711 18 10 1.167 1.545 13 10 1.117 1.365 1.633 20 11 2.335 3.661 14 11 2.353 2.671 3.175 22 12 4.335 5.723 15 12 4.767 5.723 6.265 24 13 10.533 17.661 16 13 10.533 10.675 17.661 24 nguồn:Odenwalder(1970) và Larsen(1973)