Chương 1: Tổng quan về mã hóa kênh – Tài liệu text

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản không thiếu của tài liệu tại đây ( 2 MB, 68 trang )

Đại học Công Nghệ – Đại học Quốc gia Hà Nội

được biểu diễn bằng 4, 8 hoặc nhiều hơn nữa các ký hiệu. Với hệ thống dùng mã hóa

kênh, ở phía thu chúng ta không tách các bit thông tin thực tế mà thay vào đó là các ký

hiệu mã hóa để từ các ký hiệu đó chúng ta có thể khôi phục lại các bit thông tin gốc… Có

hai loại mã hóa kênh chính là mã khối (block code) và mã chập (convolutional code).

Mã khối tiến hành trên từng khối bản tin k bit, cho thêm (n – k) bit dư tạo nên từ mã

n bit có tốc độ bit R0 = (n/k)Rs

Rs

: Tốc độ nguồn thông tin.

R0

: Tốc độ dữ liệu kênh.

R = k/n

: Tốc độ mã.

Có nhiều loại mã khối, như:

• Mã tuần hoàn (Cyclic codes) (Mã Hamming là một bộ phận nhỏ của mã tuần

hoàn)

• Mã lặp (Repetition codes)

• Mã chẵn lẻ (Parity codes)

• Mã Reed-Solomon (Reed Solomon codes)

• Mã BCH (BCH code)

• Mã Reed-Muller

Mã Xoắn (Convolutional code) có thể coi là chập giữa dãy lối vào và đáp ứng xung

của bộ mã. Độ dài của đáp ứng xung bằng bộ nhớ của bộ mã. Mộ mã dùng cửa sổ trượt

trên dãy bản tin đến, độ rộng cửa sổ bằng độ dài bộ nhớ. Như vậy khác với mã khối, mã

Xoắn nhận bản tin như dãy liên tục và cho bit mã ra cũng liên tục với tốc độ cao hơn. Mã

Turbo được phát triển dựa trên mã Xoắn, gồm hai mã Xoắn đệ quy hệ thống RSC kết nối

song song, phân biệt nhờ bộ xáo trộn giả ngẫu nhiên và thuật toán giải mã lặp với chất

lượng tiến tới tiệm cận Shannon.

Trong khuôn khổ của luận án, tôi chỉ trình bày về một số mã điển hình là mã

Hamming, mã Convolutional và mã Turbo.

9

Đại học Công Nghệ – Đại học Quốc gia Hà Nội

Chương 2: Mã Hamming

2.1: Giới thiệu chung:

Trong những năm của thập niên kỷ 1940, Hamming làm việc tại Bell Labs trên máy

tính Bell Model V và một máy điện cơ (electromechanical) dùng rơ-le với tốc độ rất

chậm, mấy giây đồng hồ một chu kỳ máy. Nhập liệu được cho vào máy bằng những cái

thẻ đục lỗ (punch cards), và hầu như máy luôn luôn gây lỗi trong khi đọc. Trong những

ngày làm việc trong tuần, những mã đặc biệt được dùng để tìm ra lỗi và mỗi khi tìm

được, nó nhấp nháy đèn báo hiệu, báo cho người điều khiển biết để họ sửa, điều chỉnh

máy lại. Trong thời gian ngoài giờ làm việc hoặc trong những ngày cuối tuần, khi người

điều khiển máy không có mặt, mỗi khi có lỗi xảy ra, máy tính tự động bỏ qua chương

trình đương chạy và chuyển sang công việc khác.

Hamming thường làm việc trong những ngày cuối tuần và ông càng ngày càng trở

nên bực tức mỗi khi ông phải khởi động lại các chương trình ứng dụng từ đầu, do chất

lượng kém, không đáng tin cậy của bộ máy đọc các thẻ đục lỗ. Mấy năm tiếp theo, ông

dồn tâm lực vào việc xây dựng hằng loạt các thuật toán có hiệu quả cao để giải quyết vấn

đề sửa lỗi. Năm 1950, ông đã công bố một phương pháp mà hiện nay được biết là Mã

Hamming.

2.2: Mã Hamming:

2.2.1: Khoảng cách Hamming:

Khoảng cách Hamming được sử dụng trong kỹ thuật viễn thông để tính số lượng

các bit trong một từ nhị phân (binary word) bị đổi ngược, như một hình thức để ước

tính số lỗi xảy ra trong quá trình truyền thông, và vì thế, đôi khi nó còn được gọi là

khoảng cách tín hiệu (signal distance). Việc phân tích trọng số Hamming của các bit

còn được sử dụng trong một số ngành, bao gồm lý thuyết tin học, lý thuyết mã hóa, và

10

Đại học Công Nghệ – Đại học Quốc gia Hà Nội

mật mã học.

Trước tiên ta tìm hiểu về trọng số Hamming: trọng số Hamming của một từ mã là

số số 1 có trong từ mã đó. Ví dụ với từ mã 00111010 có trọng số Hamming là 4.

Khoảng cách Hamming được định nghĩa là các bít khác nhau giữa hai từ mã. Khoảng

cách Hamming giữa hai từ mã được lấy bằng cách dùng toán tử XOR từng bít của hai

từ mã với nhau và khoảng cách Hamming là trọng số của kết quả tìm được trong phép

XOR trên. Ví dụ ta có hai từ mã 0110101 và 1110001 ta có:

0110101

XOR

1110001

—————1000100

Vậy khoảng cách Hamming của 2 từ mã trên là 2.

2.2.2: Thuật toán:

Mã Hamming là một mã sửa lỗi tuyến, mã này có thể phát hiện một bit hoặc hai bit

bị lỗi. Mã Hamming còn có thể sửa các lỗi do một bit bị sai gây ra.

Có thể tóm tắt các bước cho việc sử dụng mã Hamming như sau:

1) Các vị trí trong một khối được bắt đầu đánh số từ 1: Bit 1, 2, 3…

2) Tất cả các bít ở vị trí số mũ của 2 được dùng làm bít chẵn lẻ.

Vd: 2 0, 21, 22, 23,

24…

3) Tất cả các vị trí khác vị trí còn lại sẽ được dùng cho các bit dữ liệu. VD: vị trí thứ

2, 3, 5, 6, 7…

4) Mỗi bit chẵn lẻ tính giá trị chẵn lẻ cho một số bit trong từ mã theo quy tắc như

sau:

• Bít chẵn lẻ ở vị trí số 1 (2 0) sẽ kiểm tra tính chẵn lẻ của các vị trí mà số thứ tự của

vị trí đó trong hệ nhị phân có bít ngoài cùng là 1. Vd: 1 (1), 3 (11), 5 (101), 7 (111), 9

(1001) ..

11

Đại học Công Nghệ – Đại học Quốc gia Hà Nội

• Bít chẵn lẻ ở vị trí số 2 (10) sẽ kiểm tra tính chẵn lẻ của các vị trí mà số thứ tự

của vị trí đó trong hệ nhị phân có bít thứ 2 là 1. Vd: 2 (10), 3 (111), 6 (110), 7 (111), 10

(1010)…

• Bít chẵn lẻ ở vị trí số 4 (100) sẽ kiểm tra tính chẵn lẻ của các vị trí mà số thứ tự

của vị trí đó trong hệ nhị phân có bít thứ 3 là 1. Vd: 4, 5, 6, 7, 12, 13, 14, 15…

• Tương tự với các bít chẵn lẻ ở vị trí cao hơn: 8, 16, 32…

• Tóm lại, mỗi bít chẵn lẻ trong mã Hamming sẽ tính giá trị chẵn lẻ mà tại đó, bit

nhị phân của vị trí AND với các bit vị trí sẽ là một số khác không.

2.2.3: Ví dụ đối với mã ASCII 7 bit:

Mã ASCII 7 bit cần 4 bit dư thừa để thêm vào dữ liệu gốc. Sở dĩ ta chọn là 4 bít vì

24 = 16 sẽ xác định được 16 trường hợp bị lỗi đơn bít (trong dãy ta xét có 11 bit: 7 bit dữ

liệu và 3 bit mã).

Các bít dư thừa được đặt vào vị trí 1, 2, 4 và 8.

11

7

d

10

6

d

9

5

d

8

4

p

7

4

d

6

3

d

5

2

d

4

p

3

3

1

d

2

2

p

1

p

1

Trong đó, bit R được dùng để tính chẵn lẻ các tổ hợp bít sau:

• Bit p1 tính các bit thứ 3, 5, 7, 9, 11

• Bit p2 tính các bit thứ 3, 6, 7, 10, 11

• Bit p3 tính các bit thứ 5, 6, 7

• Bit p4 tính các bit thứ 9, 10, 11

12

Đại học Công Nghệ – Đại học Quốc gia Hà Nội

Hình 2.1: Vòng tròn trong mã Hamminh

Ví dụ, ta có chuỗi bit “1010110” và mã Hamming sử dụng bít chẵn lẻ chẵn thì

p1 = 1, p2 = 0, p3 = 0, p4 = 0

Khi đó, chuỗi dữ liệu truyền đi sẽ là 10100100110

13

Đại học Công Nghệ – Đại học Quốc gia Hà Nội

Hình 2.2: Vòng tròn Hamming

Do mã hamming sử dụng bit chẵn-lẻ-chẵn nên tổng số bít 1 trong 1 vòng tròn là số

chẵn. Giả sử trong quá trình truyền xảy ra lỗi tại bit 11, tại phía thu, thuật toán sẽ phát

hiện ra tổng số bit 1 trong 3 vòng tròn (vòng bên trái và hai vòng trên dưới) là một số lẻ,

trái với quy tắc nên nó sẽ thay đổi giá trị của bít nằm ở vùng giao của 3 vòng tròn này.

Hình 2.3: Bit thứ 11 bị lỗi khiến tổng số bít 1 của 3 vòng tròn bên phải

là một số lẻ

2.2.4: Mô tả bằng thuật toán:

Như ta đã biết, mã Hamming là một mã khối. Và với mọi m > 2, luôn tồn tại mã

Hamming với các thông số sau:

• Chiều dài từ mã: n = 2m-1

14

Đại học Công Nghệ – Đại học Quốc gia Hà Nội

• Chiều dài phần tin: k=2m-m-1

• Chiều dài phần kiểm tra: m=n-k

• Khả năng sửa sai: t=1

• Ma trận kiểm tra H có dạng: H = [Im.Q]

Trong đó Im là mà trận đơn vị m*m và Q là ma trận [2 m-m-1] cột, mỗi cột là vectơ m

chiều có trọng số là 2 hoặc lớn hơn.

Ví dụ, với m=3, ma trận của mã [7,4] được viết dưới dạng

1 0 0 1 0 1 1

H(3,7) = 0 1 0 1 1 1 0

0 0 1 0 1 1 1

Trong thực tế, để việc tạo và giải mã Hamming một cách đơn giản, người ta đổi vị

trí các cột trong ma trận H. Khi đó, các bit kiểm tra xen kẽ với các bit mang tin.

Để việc tạo các mã đơn giản, ta chọn các bit kiểm tra x, y, z ở các vị trí tương ứng 2 i

với i=0, 1, 2… nghĩa là tại các vị trí thứ nhất, thứ hai và thứ tư của các ký hiệu (đối với

khối có 4 bit dữ liệu): t=(x, y, u0 ,z, u1, u2, u3 )

a) Tạo mã:

0 0 1

0 1 0

0 1 1

t.Ht = | x y u0 z u1 u2 u3 |. 1

0 0 =0

1 0 1

1 1 0

1 1 1

z + .1+ .1+ .1=

u2

u3

0

 u1

y .1+ 0 .1+z .1+ 2 .1+ 3 .1=

u

u

u

0

x .1+ 0 .1+z .1+ 1 .1+ 3 .1=

u

u

u

0



15

Đại học Công Nghệ – Đại học Quốc gia Hà Nội

z = + +

 u1 u2 u3

y = 0 + 2 + 3

u

u

u

x = 0 + 1 + 3

u u

 u

Ví dụ: Tin cần phát đi là

U = (u0, u1, u2, u3) = (1 0 1 1)

Ta có:

x = u 0 + u 1 + u3 = 1 + 0 + 1 = 0

y = u 0 + u 2 + u3 = 1 + 1 + 1 = 1

z = u 1 + u2 + u 3 = 0 + 1 + 1 = 0

vậy từ mã phát đi sẽ là : t = (0 1 1 0 0 1 1)

b) Giải mã tại bên thu :

0

0

0

t

s = r. H = |r0 r1 r2 r3 r4 r5 r6|. 1

1

1

1

0

1

1

0

0

1

1

1

0

1

0

1

0

1

= (S0, S1, S2)

s

r

r

 0 =r3 +r4 + 5 + 6



s

r

r

 1 =r + 2 +r5 + 6

1

 =r + + +

s

r2

r4

r5

0

2

Ví dụ: Tín hiệu thu được là

R = (r0, r1, r2, r3, r4, r5, r6) = (0 0 1 0 0 1 1)

Khi đó:

s0=1+0+1+1=1

s1=0+1+1+1=1

16

Đại học Công Nghệ – Đại học Quốc gia Hà Nội

s2=0+1+0+1=0

Ta có S = (1 1 0), đổi sang thập phân thì S = 6, tức là bít thứ 6 (tương ứng với r 1) bị

lỗi, đảo bít này ta thu được chuỗi bít đúng là R = (0 1 1 0 0 1 1).

2.3: Kết luận

Có thể nói, lịch sử phát triển của mã sửa lỗi được bắt đầu bằng sự ra đời của mã

Hamming và định lý Shannon. Việc ra đời mã Hamming là cơ sở cho việc phát triển thêm

nhiều loại mã hóa mới, có độ tin cậy cao hơn sau này. Mã Hamming có tầm quan trọng

cơ bản trong lý thuyết mã hóa và được sử dụng thực tế trong thiết kế máy tính. Ưu điểm

của mã này là đơn giản, số bit kiểm tra ít, ngoài ra, mã này hoạt động tốt trong việc phát

hiện các lỗi đơn bit và một số trường hợp lỗi hai bit. Tuy nhiên, mã Hamming không thể

sửa được bản tin bị lỗi đa bit.

Chương 3: Mã Xoắn

3.1: Giới thiệu chung:

Như ta đã biết, xác suất xảy ra lỗi có thể được giảm bằng cách truyền nhiều bít hơn

số bít cần thiết, và các bít cạnh nhau phải có sự liên quan nào đó với nhau để nếu có lỗi

xảy ra thì sẽ đủ thông tin để xác định ra bít bị lỗi. Đối với mã khối, chúng được coi là các

mã không có sự ghi nhớ, với ý nghĩa là từ mã hoặc các bít dư được thêm vào chỉ là một

hàm của khối bít hiện tại. Trái lại, các mã xoắn hoạt động có sự ghi nhớ. Đối với mã

xoắn, các bit sau khi mã hóa là các hàm của các bit thông tin và các hàm của độ dài giới

hạn (constraint length). Đặc biệt, mỗi bit sau khi mã hóa (tại đầu ra của bộ mã hóa xoắn)

là tổ hợp tuyến tính của một số bit thông tin trước đó.

17

Đại học Công Nghệ – Đại học Quốc gia Hà Nội

Trong mã xoắn, tỉ lệ R = bit thông tin / bit truyền gọi là tỷ lệ mã hóa (code rate), tỷ

lệ này nhỏ hơn 1. Còn số bit thông tin xảy ra mã xoắn là độ dài giới hạn k (contraint

length).

Ví dụ, ta sẽ mã hóa một bản tin sử dụng mã xoắn, với tỷ lệ mã hóa là R = 0.5 thì với

mỗi 1 bit thông tin sẽ có 2 bit được truyền đi và sử dụng độ dài giới hạn k=3. Khi đó, bộ

mã hóa xoắn sẽ gửi ra ngoài 16 bit với mỗi 8 bit thông tin đầu vào, với mỗi 1 cặp bit ra sẽ

phụ thuộc vào bit đầu vào hiện tại và 2 bit trước đó (vì độ dài giới hạn k=3).

Hình3.15: Mã xoắn với tốc độ mã R=0.5 và k=9

Ta có thể thấy là với phương pháp mã hóa này thì mỗi bít thông tin đầu vào sẽ ảnh

hưởng tới 6 bít đầu ra.

3.2: Mã Xoắn:

3.2.1: Ví dụ về mã xoắn:

Để làm rõ hơn phương thức hoạt động của mã xoắn, ta xét một bộ mã xoắn có tốc

độ mã k=0.5.

18

Đại học Công Nghệ – Đại học Quốc gia Hà Nội

Hình 3.2: Sơ đồ khối của mã xoắn

Với k=0.5 thì với mỗi bit đầu vào sẽ có 2 bit đầu ra. Ta có:

z1 = x(n) ⊕ x(n-1) ⊕ x(n-2)

z2 = x(n) ⊕ x(n-2)

Đầu vào được nối với các bộ XOR có thể được viết dưới dạng các vector nhị phân

[1 1 1] và [1 0 1], các vector này được gọi là các vector sinh.

3.2.2: Giải mã bằng sơ đồ trạng thái:

Dưới đây là sơ đồ trạng thái của bộ mã xoắn

19

Xem thêm: Tìm việc Làm Giám đốc Đầu tư và Phát triển Dự án Tuyển Dụng 19/04/2023 | https://thomaygiat.com

Source: https://thomaygiat.com
Category : Kỹ Thuật Số