Phụ lục
Phụ lục 5A

CÁC VÍ DỤ MINH HỌA CHO MÃ KHỐI TUYẾN TÍNH
VD PL5.1: Xét một họ mã được gọi là mã Hamming có các tham số sau
Độ dài từ mã:
n = 2m − 1
Số các bit bản tin:
k = (2 m − 1) − m
m=n−k
Số các bit chẵn lẻ:
Trong đó m ≥ 3.
Cụ thể xét mã Hamming (7,4) có n=7; k=4 tương ứng có m= 3.
Ma trận tạo mã của mã này phải có cấu trúc phù hợp với (5.14) và có dạng.

1

0
G = 
1

1


1
1
1
0
P

0:1

1 :0
1 :0
1 :0

0
1
0
0

0
0
1
0
Ik


0

0
0

1


Ma trận kiểm tra chẵn lẻ có dạng


1 0 0 : 1 0 1 1



H = 0 1 0 : 1 1 1 0
0 0 1 : 0 1 1 1


PT
 In−k


Các từ mã được tạo ra theo (5.15) C=mG và được cho ở bảng 5A1:
Quan hệ giữa dmin và H
Do c là một từ mã thuộc mã nên c.H T = mGH T = 0 ⇒ Xét mã Hamming (7,4), tồn tại
16 từ mã thuộc mã đều làm cho s = c.H T = 0 trong đó có
Bẩy từ mã có trong lượng = 3
Bẩy từ mã có trọng lượng = 4
Một từ mã có trọng lượng = 7
Một từ mã có trọng lượng = 0
⇒ dmin =3 ⇒ Mối quan hệ giữa dmin và H là: dmin là số cột nhỏ nhất của ma trận kiểm tra
chẵn lẻ H mà khi cộng chúng với nhau bằng 0. Chẳng hạn cho từ mã c = 0110100.
Sử dụng công thức c.H T = mGH T = 0


1 0 0 : 1 0 1 1 


C.H T = [0 1 1 0 1 0 0 ]1×7 0 1 0 : 1 1 1 0
0 0 1 : 0 1 1 1 


PT
 In−k



-348-

T


Phụ lục
sau đó loại bỏ các cột của H tương ứng các vị trí có bit bằng 0 của từ mã nhận được tổng
của các cột thứ 2 và thứ 3 và thứ 5 của H như sau:
0 0 0 0
1  + 0 + 1 = 0
       
0 1 1 0

⇒ Vậy Syndrome = [0 0 0].
Nếu thực hiện cho 14 từ mã khác không còn lại thuộc mã thì Syndrome đều bằng 0.
Bảng 5A1. Các từ mã của mã Hamming (7,4)
Bản tin
Từ mã
Trọng
Bản tin
Từ mã
Trọng
lượng
lượng
0000
0000000
0
1000

1101000
3
0001
1010001
3
1001
0111001
4
0010
1110010
4
1010
0011010
3
0011
0100011
3
1011
1001011
4
0100
0110100
3
1100
1011100
4
0101
1100101
4
1101

0001101
3
0110
1000110
3
1110
0101110
4
0111
0010111
4
1111
1111111
7
Cho thấy, trọng lượng nhỏ nhất của các từ mã khác không là 3 ⇒ khoảng cách Hamming
cực tiểu là dmin =3. Tất nhiên các mã Hamming có thuộc tính là khoảng cách Hamming
cực tiểu luôn bằng 3 không phụ thuộc vào m. Do dmin =3 nên theo (5.1) và (5.2) các mã
này chỉ có thể sửa được một lỗi và phát hiện được hai lỗi.

C1×n = m 1× k .G k× n = 
b
:
 (n − k) bit kiÓm tra
⇒ C i = m i .G ,

Chẳng hạn: c1×7





k bit b¶ n tin 

m

i = 0,1,...,2 k − 1

1

0
= [1 0 0 1]1×4 
1

1



1 0 : 1 0 0 0

1 1 : 0 1 0 0


= 011 1001

1 1:0 0 1 0
m 
 b

0 1 : 0 0 0 1
 4×7
P

Ik

Quan hệ giữa Syndrome mẫu lỗi e
Xét mã Hamming (7,4). Vì mã này có dmin =3 nên chỉ có thể sửa được một lỗi ⇒ nên
với các mẫu lỗi đơn, áp dụng thuộc tính 3 (Syndrome là tổng các cột của ma trận H tương
ứng với nơi xẩy ra lỗi) ⇒ cho phép xác định được quan hệ giữa Syndrome và mẫu lỗi.
Chẳng hạn
Nếu truyền c = [1 1 1 1 1 1 1] qua kênh, phía thu nhận được y = [1 1 1 1 0 1 1], xảy
ra lỗi ở vị trí thứ 5 của c ⇒ theo thuộc tính 3 thì Syndrome sẽ là cột thứ 5 của ma trận H
nghĩa là

-349-


Phụ lục

1 0 0 : 1
T
S = y.H = [1 1 1 1 0 1 1] × 0 1 0 : 1

0 0 1 : 0

1 0 0 1  1 1
= 0 + 1 + 0 + 1  + 1 + 0
0 0 1 0 1 1
=

0
1
1

Note


1 1
1 0

1 1


T

0
1
 
1
Cét thø 5 cña H

khi biết được Syndrome thì biết được vector mẫu lỗi là e = [0 0 0 0 1 0 0] ⇒ sửa được lỗi ở
vị trí 5 này ycor = y + e = [1 1 1 1 0 1 1] + [0 0 0 0 1 0 0] = [1 1 1 1 1 1 1]
Bảng 5A2. Bảng giải mã cho mã Hamming (7.4)
Syndrome
Mẫu lỗi
000
0000000
100
1000000
010
0100000
001
0010000

110
0001000
011
0000100
111
0000010
101
0000001
Nếu phát c = [0111001] qua kênh, phía thu nhận được y = [1111001] ⇒ s = [1 0 0] là
hàng thứ nhất của HT (cột thứ nhất của H) ⇒ xác định được e = [1 0 0 0 0 0 0] ⇒ sửa được
ycor = [0111001].
Tương tự xét tất cả các trường hợp còn lại ⇒ Quan hệ này đối với mã Hamming
(7,4) được cho ở bảng 5A2 ⇒ Từ mã sai là từ mã không thuộc mã đó, khi này S = y.HT ≠ 0
vì c.HT =0
VD PL 5.2: Các mã Hamming
Để minh hoạ việc trình bầy mã vòng ở dạng đa thức, ta khảo sát quá trình tạo ra mã
vòng (7,4) cho mã Hamming. Với độ dài từ mã n=7, thực hiện khai triển đa thức 1 + x 7 vào
ba đa thức thừa số tối giản như sau

(

)(

x 7 + 1 = (1 + x ) 1 + x 2 + x 3 1 + x + x 3

)

Đa thức tối giản là đa thức không thể phân chia thành thừa số bằng cách sử dụng các
đa thức có các hệ số là mã cơ số hai. Một đa thức tối giản bậc m được gọi là đa thức
nguyên thuỷ nếu tồn tại quan hệ n = 2 m − 1 , trong đó n là bậc của đa thức 1 + x n chia hết cho

đa thức nguyên thuỷ. Vậy ở ví dụ đang xét chỉ có hai đa thức nguyên thuỷ là
(1 + x 2 + x 3 ) vµ (1 + x + x 3 ).
Các đa thức g(x) và h(x)
Nếu chọn đa thức tạo mã g(x) với bậc bằng số các bit chẵn lẻ (n-k) bởi

-350-


Phụ lục
g(x) = 1 + x + x 3

thì đa thức kiểm tra chẵn lẻ h(x) sẽ là

(

h ( x ) = (1 + x ) 1 + x 2 + x 3

)

=1 + x + x2 + x4

có bậc bằng số các bit bản tin (k bit).
Quá trình tạo từ mã c(x) theo đa thức tạo mã g(x)
Xét các thủ tục tạo mã cho khối bản tin m = 1001 bằng cách sử dụng đa thức tạo mã
nói trên.
Viết khối bản tin như sau:
m( x ) = 1 + x 3

Nhân đa thức bản tin với x n − k = x 3 nhận được


(

)

x 3 .m( x ) = x 3 1 + x 3 = x 3 + x 6

Chia đa thức trên cho đa thức tạo mã g(x) để nhận được phần dư b(x), kết quả được
x n −k m ( x )

b(x)

x3 + x6
x + x2
3
=x+x +
1 + x + x3
1 + x + x3
a(x)
g(x)

g(x)

Đa thức tạo mã c(x) được xác định theo (5.39):

c( x ) = b( x ) + x n −k .m( x )
= x + x2 + x3 + x6
b(x )

x n − k .m ( x )
0.x 0 +1.x1 +1.x 2 +1.x 3 + 0.x 4 + 0.x 5 +1.x 6


Kết quả ta được từ mã là c = 0 1 1

1 0 0 1 là từ mã có trong bảng 5A.1

( n − k )=3 bit

kiÓm tra ch½n lÎ

k = 3 bit cña
khèi b¶ n tin

cho mã Hamming (7,4).
⇒ Tổng quát hoá: Mọi mã vòng được tạo ra bởi một đa thức nguyên thuỷ là một mã
Hamming có khoảng cách hamming cực tiểu dmin=3.
Quan hệ giữa g(x) với G và h(x) với H
Sẽ thấy rằng, đa thức tạo mã g(x) và đa thức kiểm tra chẵn lẻ h(x) xác định đơn trị
ma trận tạo mã G và ma trận kiểm tra chẵn lẻ H từ ví dụ này.
Xây dựng ma trận tạo mã G từ đa thức tạo mã g(x).
Để xây dựng ma trận tạo mã G kích thước 4×7 ta bắt đầu bằng việc khảo sát bốn đa
thức gồm đa thức tạo mã g(x) và ba đa thức dịch vòng của đa thức tạo mã g(x)

-351-


Phụ lục
g(x )

=1+ x + x3


x.g ( x ) = x + x 2 + x 4
x 2 g(x ) = x 2 + x 3 + x 5
x 3 g(x ) = x 3 + x 4 + x 6

Từ thuộc tính dịch vòng thấy rõ các đa thức g(x); xg(x);x2g(x) và x3g(x) là các đa
thức từ mã của mã Hanning (7,4). Nếu sử dụng các hệ số của các đa thức nói trên cho các
hàng của ma trận 4×7 nhận được.
1
0
G=
0

0

1 0 1 0 0 0
1 1 0 1 0 0
0 1 1 0 1 0

0 0 1 1 0 1

Để nhận được dạng hệ thống, cộng hàng thứ nhất vào hàng thứ 3 rồi cộng tổng của
hai hàng đầu với hàng thứ 4, ta được.
1
0
G=
1

1

1 0 1 0 0 0

1 1 0 1 0 0
1 1 0 0 1 0

0 1 0 0 0 1

ma trận này giống hệt như ma trận ở VDPL 5.1.
Xây dựng ma trận kiểm tra chẵn lẻ H từ đa thức kiểm tra h(x).
Trước hết, xét đa thức đảo của h(x) được định nghĩa là x k .h ( x −1 ) , các đa thức này
cũng là các đa thức thừa số của 1 + x n . Trong trường hợp này, ma trận H có kích thước là
3×7, vì vậy cần phải thiết lập ba đa thức gồm đa thức x 4 .h ( x −1 ) và hai đa thức dịch vòng
của nó như sau.
x 4 h ( x −1 )

=1+ x2 + x3 + x4

x 5 .h ( x −1 )

= x + x3 + x4 + x5

x 6 h ( x −1 )

= x2 + x4 + x5 + x6

Nếu sử dụng các hệ số của các đa thức này cho các hàng của ma trận 3×7 nhận được
ma trận H như sau:
1 0 1 1 1 0 0
H = 0 1 0 1 1 1 0
0 0 1 0 1 1 1

Biến đổi ma trận H vào dạng hệ thống. Muốn vậy, cộng dòng thứ 3 vào dòng thứ

nhất kết quả thế vào dòng thứ nhất nhận được H ở dạng hệ thống giống như H ở VDPL5.1
như sau:
1 0 0 : 1 0 1 1
H = 0 1 0 : 1 1 1 0
0 0 1 : 0 1 1 1

-352-


Phụ lục
VDPL 5.3: Bộ lập mã vòng Hamming (7,4)
Sơ đồ bộ lập mã vòng Hamming (7,4) có đa thức tạo mã g ( x ) = 1 + x + x 3 được cho ở
hình A1:
CM1

C¸c bit
kiÓm tra
ch½n lÎ

F-F

F-F

F-F
CM2
Tõ m·

C¸c bit b¶n tin

Hình 5A1. Bộ lập mã vòng (7,4) với g ( x ) = 1 + x + x 3

Để mô tả hoạt động của bộ lập mã này xét chuỗi bản tin đầu vào là (1001). Thay đổi
nội dung của thanh ghi dịch sau mỗi lần dịch vào một bit thông tin được cho ở bảng 5A3.
Sau bốn lần dịch nội dung của thanh ghi dịch và các bit chẵn lẻ tương ứng là (0111). Vậy
nếu gắn các bit này vào các bit tin nhận được từ mã (0111001) kết quả này giống hệt ở
VDPL 5.1.
Bảng 5A3. Nội dung thanh nghi dịch cho VDPL5.3 khi bản tin vào (1001)
Bit vào
Nội dung thanh ghi
Dịch
1
1
110
2
0
011
3
0
111
4
1
011
VDPL 5.4: Bộ tính Syndrome cho mã vòng (7,4)
Đối với mã Hamming vòng được tạo bởi bộ tạo mã g(x)=1+x+x3 sơ đồ tính
Syndrome được cho ở hình A2. Giả sử từ mã phát là (0111001) và từ mã thu là (0110001);
nghĩa là bít giữa bị sai. Nội dung thanh ghi dịch của bộ tính Syndrome trong trường hợp
này được cho ở bảng 5A4.
CM1

C¸c bit thu


F-F

F-F

F-F
Syndrome

Hình 5A2. Bộ tính Syndrome cho mã (7,4) được tạo bởi đa thức g(x)=1+x+x3.

-353-


Ph lc
Bng 5A4. Ni dung b tớnh Syndrome hỡnh PL5A2, t mó thu (0110001)
Dch
Bit vo
Ni dung thanh ghi
000 (trng thỏi u)
1
1
100
2
0
010
3
0
001
4
0
110

5
1
111
6
1
001
7
0
110
Sau by ln dch Syndrome c xỏc nh bng 110. Vỡ Syndrome khỏc khụng nờn
t mó thu b mc li. T bng 5A4 nhn c mu li tng ng l 0001000 ngha l bit
gia b li.

PHT HIN V SA LI CA M KHI TUYN TNH
Mó kim tra chn l
Nu tt c cỏc li bit l ng kh nng v c lp thng kờ, thỡ xỏc sut xy ra j li
trong mt khi n l:

p ( j, n )
Xác suất xảy ra j bit lỗi
trong một khối n bit mã

=

n

j

p


j

(1 p )

xác suất một xác suất một bit
bit bị lỗi
không bị lỗi
Số trờng hợp j bits bị lỗi
trong n bit mã

n

n j

(5A.1)

n!

l s trng hp j bit mó
trong ú: p l xỏc sut mt ký hiu kờnh b li; =
j j!(n j)!
trong s n bit mó b li. Do vy, i vi mó n phỏt hin li kim tra chn l, xỏc sut li
khụng th phỏt hin c Pnd ca khi n bits c tớnh nh sau:

Pnodetect

n/2 n 2j
n 2 j
p (1 p) ,
2

j
j=1
=
(n 1) / 2
n 2j

n 2 j
p (1 p) ,

2
j
j=1

trờng hợp n lẻ

(5A.2)
trờng hợp n chẵn

Mó mó khi
Mó khi cũn c gi l mó tớch, cú th c hiu l mt cu trỳc mó song song. Mó
khi c to ra bng cỏch: To khi cỏc bit bn tin dng hỡnh ch nht gm cú M hng v
N ct, sau ú t cỏc bit kim tra chn l vo cỏc ct v hng theo chiu ng v ngang,
kt qu nhn c mt mng (M+1)ì(N+1), t l mó l

k
MN
. Khi ny hiu
=
n (M + 1)(N + 1)


nng ca nú tt hn so vi mó n kim tra chn l. Trng hp ny nú cú kh nng sa
c mt li (nh v chớnh xỏc mt li trong khi d liu). i vi mó khi sa li, ta cú
th tớnh xỏc sut khụng th sa c li. T xỏc sut xy ra j li trong mt khi n ký hiu
theo phng trỡnh (5A.1), ta tớnh xỏc sut li bn tin (hay xỏc sut li khi, li t mó) i
vi mó sa c t li l:

-354-


Phụ lục

PM =

n j
n− j
∑
  p (1 − p )
j= t +1  j 
n

(5A.3)

trong đó P là xác suất một ký hiệu kênh bị lỗi.

Phát hiện lỗi và sửa lỗi
Mã khối tuyến tính (n,k) sửa t lỗi có khả năng sửa được 2n −k mẫu lỗi. Nếu dùng mã
khối sửa t lỗi để sửa lỗi trên kênh nhị phân đối xứng BSC có xác suất truyền p, thì xác suất
lỗi bản tin PM mà bộ giải mã giải mã sai, và khối n bit bị lỗi được tính theo (5A.3) làm giới
hạn trên:
n

n− j

PM ≤ ∑   p j (1 − p )
j
j= t +1  
n

(5A.4)

Dấu “=” xảy ra khi bộ giải mã sửa được toàn bộ các tổ hợp lỗi ≤ t lỗi (nằm trong phạm vi,
khả năng sửa lỗi của mã). Xác suất lỗi bit giải mã PB, phụ thuộc vào bộ mã và bộ giải mã
được dùng. Tuy nhiên, ta thường lấy gần đúng

PB ≈

1 n n j
n− j
j   p (1 − p )
∑
j
n j= t +1  

(5A.5)

-355-


Phụ lục
Phụ lục 5B


CÁC VÍ DỤ MINH HỌA CHO MÃ XOẮN
VD PL5.5: Trình bầy hoạt động của bộ lập mã được cho ở hình 5B1 (là hình 5.11a) bằng
phương pháp ma trận tạo mã.

a)

ci,1

D
m i(1)

ra

ci,2

Vµo

m (i 2 )

D

ci,3

M = 1, k = 2, n =3, K = 2

Hình 5B1. Bộ lập mã xoắn
Bước 1: Rút ra ma trận tạo mã từ sơ đồ bộ lập mã
Phương trình vào/ra của sơ đồ lập mã
c i ,1 = m i(1) + m (i 2) + m i(1−)1 + m i(−21)
c i , 2 = m i(1−)1 + m (i 2 )


(5B.1)

c i ,3 = m (i1) + m i( 2) + m i(−21)

trong đó: mi(−q )p là các bit bản tin vào bộ nhớ p từ các đầu vào q=1, 2 ở thời điểm (i-p), p là
số thứ tự nhớ (p =1, 2), c i, j là các bit đầu ra của các bộ cộng modulo-2 thứ j (j =1, 2, 3) ở
thời điểm i, dấu cộng biểu thị cộng Modul-2.
Phương trình vào ra theo toán tử trễ x
Nếu coi x là toán tử trễ thì các phương trình (5.48) được viết dưới dạng
c i ,1 = m i(1) (1 + x ) + m (i 2) (1 + x )
m i(1) + m i(1−)1

m i( 2 ) + m (i −21)

c i , 2 = m i(1) .x + m i( 2)
m (i 1−)1

c i ,3 = m i(1) +

(5B.2)

m (i 2 ) (1 + x )
m i( 2 ) + m i( −21) = m i( 2 ) + m i( 2 ) .x
= m i( 2 ) (1+ x )

Kích thước và giá trị cụ thể cho các phần tử của ma trận tạo mã G
Kích thước và các phương trình vào/ra theo các phần tử của G.

-356-



Phụ lục
Từ các phương trình tổng quát và các tham số đặc trưng cho sơ đồ này (k=2,
n=3,M=1,K=2), nhận được kích thước và các phần tử của ma trận tạo mã G tương ứng
cũng như các phương trình vào ra được viết theo các phần tử của ma trận G như sau

(

c i = m (i1) , m i( 2)

)

1× 2

 g (p1,)1
×  ( 2)
g p ,1

= (c i ,1 , c i , 2 , c i ,3 )1×3

g (p1,)3 

g (p2,3) 
2×3

g (p1,)2
g (p2, 2)

(5B.3)


c i,1 = m i(1) .g (p1,)1 + m i( 2) .g (p2,1)
c i, 2 = m i(1) .g (p1,)2 + m i( 2) .g (p2, 2)

(5B.4)

c i,3 = m i(1) .g (p1,)3 + m i( 2) .g (p2,3)

Giá trị cụ thể cho các phần tử của ma trận tạo mã G:
Bằng cách so sánh các phương trình vào ra của sơ đồ theo các phần tử của ma trận
tạo mã G với các phương trình vào ra theo toán tử trễ x rút ra được giá trị cụ thể cho các
phần tử của ma trận tạo mã cần tìm.
So sánh biểu thức (5B.2) với (5B.3) & (5B.4) ta được
c i,1 = m (i1) (1 + x ) + m i( 2) (1 + x )
m i(1) + m i(1−)1

⇔ c i,1 = m i(1) .g (p1,)1 + m i( 2) .g (p2,1)

m i( 2 ) + m (i −21)

c i, 2 = m i(1) .x + m (i 2 )
m i(1−)1

c i,3 = m (i1) +

⇔ c i, 2 = m i(1) .g (p1,)2 + m i( 2) .g (p2, 2)

m i( 2) (1 + x )

(5B.5)


⇔ c i ,3 = m i(1) .g (p1,)3 + m i( 2) .g (p2,3)

m i( 2 ) + m i( −21) = m i( 2 ) + m i( 2 ) . x
= m i( 2 ) (1+ x )

 g (p1,)1
G =  ( 2)
g p,1

g (p1,)2
g (p2, 2)

g (p1,)3 

g (p2,3) 

2×3

1 
1 + x x
=

1 + x 1 1 + x  2×3

(5B.6)

Bước 2: Ma trận kiểm tra chẵn lẻ H
Do mối quan hệ giữa ma trận kiểm tra chẵn lẻ H và ma trận tạo mã G thông qua ma
trận P như sau. Biến đổi G vào dạng hệ thống nhận được

1 0 :
G=
0 1 :

(1 + x )−1 + x 2 (1 + x )−2  = [I : P ]

2× 2
2×1 2×3
−1
x (1 + x )
 2×3

(5B.7)

Ma trận kiểm tra chẵn lẻ có dạng:




−1
T
2
−2
−1



H = P2×1 : I1
= (1 + x ) + x (1 + x )
x (1 + x ) : 1 


(n − k =1)× k (n − k )=1
I1 
P2T×1
1×3 

1×3

(5B.8)

Loại bỏ mũ âm bằng cách nhân ma trận trên với (1+x)2 ta được:
H = 1 + x + x 2 , x(1 + x),


(1 + x )

2




Bước 3: Dạng hồi tiếp của sơ đồ lập mã

-357-

(5B.9)


Phụ lục
Bằng cách dùng phương trình c i H T = 0 , tìm được phương trình thiết kế sơ đồ hồi tiếp

của bộ lập mã.
Từ phương trình c i H T = 0 , nhận được phương trình:
c i ,1 + c i −1,1 + c i − 2 ,1 + c i −1, 2 + c i − 2 , 2 + c i ,3 + c i − 2 ,3 = 0

trong đó c i − p , j là bit đầu ra j tại thời điểm i-p
Từ phương trình này ta có thể thiết kế dạng hồi tiếp của bộ tạo mã ở hình 5B2
m i( 2 )

Vµo

ci,3

m (i1)

ci,2
Ra

D

ci,1

D

Hình 5B2. Dạng hồi tiếp của bộ lập mã xoắn
Cả sơ đồ truyền thẳng và hồi tiếp đều được sử dụng để trình bày mã xoắn.
VDPL 5.6: Tìm chuỗi bit ở đầu ra của bộ tạo mã hình 5B3

Vµo
mi


ci,1

D0

D1

D2

ra

ci,2

M = 3, k = 1, n = 2, K = 3

Hình 5B3. Bộ lập mã xoắn
khi chuỗi bit đầu vào có dạng: m = (m0, m1, m2, m3, m4) = (10011) trong đó m0 là bit đầu
tiên vào bộ lập mã. Trong thí dụ này L = 5, M=3, K= 3, L+M-1 = 7, độn loại hai là (K-1)
bit "0" để cho các đoạn bản tin không ảnh hưởng lên nhau, r = 1/2. Vì vậy, sau khi độn 2
bit "0", thì bản tin khi này có độ dài là 7 bit được xác định như sau:
m=(m0, m1, m2, m3, m4,m5,m6) = (1001100)
Chuỗi tạo mã

-358-


Phụ lục
Chuỗi tạo mã
Từ các phương trình (5.51), ta có:

(


g (jq ) = g (0q, j) , g 1( ,qj) ,..., g (pq, j) ,..., g (Mq ,) j

)

trong đó g (pq, j) là đáp ứng của đầu ra bộ nhớ thứ p lên đầu vào q của bộ cộng j được xác định
0, nÕu dÇu ra bé nhí p kh«ng nèi dÕn bé céng Modul2 thø j
.
1, nÕu dÇu ra bé nhí p d−îc nèi dÕn bé céng Modul2 thø j

bởi g (pq, j) = 

Do k=1 ⇒ chỉ có một đầu vào q=1. Do đầu vào bộ lập mã không được nối đến bộ
cộng Modul2 ⇒ p=1,2,..,M. Vì vậy, áp dụng phương trình (5.51), trường hợp này ta được.

(

g (jq ) = g (0q, j) , g1( ,qj) ,..., g (pq, )j ,..., g (Mq ,) j

(

⇒ g j = g1, j , g 2, j , g 3, j ,

(

)

)

q =1, M = 3, n = 2


n=2

)

g1 = g1,1 , g 2,1 , g 3,1 , = (1,0,1)

Nh¸nh trª n
⇒
g1 = g1, 2 , g 2, 2 , g 3, 2 , = (1,1,1)

Nh¸nh d−íi

(

)

Các chuỗi bit ra của các nhánh cộng modul 2 thứ j và chuỗi bit ra
Chuỗi bit ra của các nhánh cộng Molul2 thứ j được xác định theo (5.55)


c j =  c0, j , c1, j ,..., ci , j ,..., c L + M −1, j 
=7


= (c1, j ,..., ci , j ,..., c 7, j )
Do dÇu vµo kh«ng d−îc nèi dÕn
bé céng Modul2 nª n i =1,2,..,7

trong đó ci,j là bit ra thứ i của nhánh thứ j và được xác định bởi

M

ci , j = ∑ g p , j , m i − p ,

i = 1,2,...,7;

p =1

j = 1,2
p = 1,2,..., M
m i − p = 0 khi i - p < 0 ⇔ i < p

+ Đối với nhánh trên (j=1)

c1 = (c1,1 , c 2,1 , c3,1 , c 4,1 , c5,1 , c 6,1 , c7 ,1 )

+ Đối với nhánh dưới (j=2)

c1 = (c1, 2 , c 2, 2 , c3, 2 , c 4, 2 , c5, 2 , c 6, 2 , c7 , 2 )

Chuỗi bit đầu ra của bộ lập mã c là ghép xen của các chuỗi bit của các n nhánh
cộng modul2, trường hợp này là


c =  c1,1c1, 2 , c 2,1 , c 2, 2 , c3,1 , c3, 2 ,..., c7 ,1 , c 7, 2 


2
3
7

 1


Tính các giá trị ci , j .

-359-


Phụ lục
Đối với nhánh trên (j=1), ta được
Triển khai (5.56) cho nhánh trên trong trường hợp này (lưu ý p bắt đầu từ 1 vì đầu
vào của bộ nhớ thứ nhất không đựơc nối đến nhánh cộng) nhận được:
3

c1,1 = ∑ g p,1 m1− p = g 1,1 m1−1 + g 2,1 m 1− 2 + g 3,1 m 1−3 = 1.1 + 0.0 + 1.0 = 1
p =1

=0

=0

3

c 2,1 = ∑ g p ,1 m 2− p = g 1,1 m 2−1 + g 2,1 m 2− 2 + g 3,1 m 2−3 = 1.0 + 0.1 + 1.0 = 0
p =1

=0

3


c 3,1 = ∑ g p,1 m 3− p = g 1,1m 3−1 + g 2,1 m 3− 2 + g 3,1 m 3−3 = 1.0 + 0.0 + 1.1 = 1
p =1

3

c 4,1 = ∑ g p ,1 m 4− p = g 1,1m 4−1 + g 2,1 m 4− 2 + g 3,1 m 4−3 = 1.1 + 0.0 + 1.0 = 1
p =1
3

c 5,1 = ∑ g p,1 m 5− p = g 1,1 m 5−1 + g 2,1 m 5− 2 + g 3,1 m 5−3 = 1 × 1 + 0 × 1 + 1 × 0 = 1
p =1
3

c 6,1 = ∑ g p ,1 m 6− p = g 1,1 m 6−1 + g 2,1 m 6− 2 + g 3,1 m 6−3 = 1 × 0 + 0 × 1 + 1 × 1 = 1
p =1

bit chÌn

3

c 7 ,1 = ∑ g p ,1 m 7− p = g 1,1 m 7 −1 + g 2,1 m 7 − 2 + g 3,1 m 7 −3 = 1 × 0 + 0 × 0 + 1 × 1 = 1
p =1

bit chÌn

bit chÌn

Vậy chuỗi bit ở đầu ra của nhánh trên (j=1) là:
c1 = (1011111)
Tương tự đối với nhánh dưới j=2, ta được

3

c1, 2 = ∑ g p ,1 m1− p = g 1, 2 m1−1 + g 2, 2 m1− 2 + g 3, 2 m1−3 = 1 × 1 + 1 × 0 + 1 × 0 = 1
p =1

= 0 do
i-p<0

= 0 do
i- p < 0

3

c 2, 2 = ∑ g p ,1m 2− p = g 1, 2 m 2−1 + g 2, 2 m 2− 2 + g 3, 2 m 2−3 = 1 × 0 + 1 × 1 + 1 × 0 = 1
p =1

= 0 do
i- p < 0

c3,2 = g1,2 m2 + g2,2 m1 + g3,2 m0
c4,2 = g1,2 m3 + g2,2 m2 + g3,2 m1
c5,2 = g1,2 m4 + g2,2 m3 + g3,2 m2
c6,2 = g1,2 m5 + g2,2 m4 + g3,2 m3
c7,2 = g1,2 m6 + g2,2 m5+ g3,1 m4

= 1× 0 + 1× 0 + 1× 1 = 1
= 1× 1 + 1× 0 + 1× 0 = 1
= 1× 1 + 1× 1 + 1× 0 = 0
= 1× 0 + 1× 1 + 1× 1 = 0
= 1× 0 + 1× 0 + 1× 1 = 1


Vậy chuỗi bit ở đầu ra của nhánh dưới là:
c2 = (1111001)

Chuỗi bit ở đầu ra của bộ lập mã là ghép chung của hai chuỗi c1, c2 như sau:
c = (11 01 11 11 10 10 11) có 14 bit.
Đa thức tạo mã:
Đa thức bản tin: Từ (5.60) ta có
L −1

m( x ) = ∑ m ℓ x ℓ = m 0 + m 1 x + ... + m ℓ x ℓ + ... + m L −1 x L −1
ℓ =0

với m = (10011) ⇒ m(x) = 1 + x3 + x4

-360-


Phụ lục
Đa thức tạo mã g (jq ) ( x ) q =1 = g j ( x ) : Từ ptr (5.61) ta có
g j ( x ) = g 0, j + g 1, j x + ... + g p, j x p + ... + g M , j x M
M

= ∑ g p, j x p
p =0

trong đó g p, j = 0 / 1 tương ứng với phần tử nhớ p không nối hoặc có nối vào bộ cộng thứ j
và cấu trúc của bộ lập mã. Do đầu vào không được nối đến bộ cộng mdul2 nên p=1,2,..,M;
j=1,2 nên nhận được
g1(x) = x + x3

g2(x) = x + x2 + x3
Đa thức chuỗi bit mã đầu ra thứ j bộ lập mã như sau:
c j ( x ) = m( x ).g j ( x )
= c 0, j + c 1, j x + ... + c i , j x i + ... + c L + M −1, j x L + M −1
=0

=

L + M −1

∑c
i =1

i, j

xi

trong đó hệ số c i, j = 0 / 1 tương ứng với bit i ở đầu ra j.
c1(x) = (1 + x3 + x4) ( x + x3)
= x+ x3 + x4 + x5 + x6 + x7
hay: c1 = (c1,1, c2,1, c3,1, c4,1, c5,1, c6,1, c7,1)
= ( 1 0 1 1 1 1 1)
3
4
2
3
c2(x) = ( 1 + x + x )( x + x + x )
= x + x2 + x3 + x4 + x7
=(1111001)
hay: c2 = (c1,2, c2,2, c3,2, c4,2, c5,2, c6,2, c7,2)

Cuối cùng được chuỗi đầu ra là ghép xen của hai chuỗi trên như sau:
c = ( 11 01 11 11 1010 11 )
Như vậy chuỗi bản tin vào 5 bit cộng thêm hai bit duôi bằng "0" để khởi đầu hai tầng
sau của thanh ghi dịch vào trạng thái "0" để chúng không ảnh hưởng lên chuỗi bit tiếp theo
sẽ được 7 bit. Do vậy tỷ lệ mã trong trường hợp này là r = 1/2. Trong thực tế chuỗi hay đa
thức tạo mã gj xác định độ trễ của bit vào i khi đưa lên nhánh cộng j, nên có thể dễ dàng
xác định chuỗi đầu ra của bộ lập mã bằng cách lập bảng như sau (bảng 5B1).
Bảng 5B1. Thí dụ về tính toán mã xoắn cho bộ lập mã 5.11d.

Chuỗi bản tin m
Bổ xung hai bit đuôi m'
1/ Trễ một tầng m'.x
2/ Trễ hai tầng m'.x2
3/ Trễ ba tầng m'.x3
C1 = 1/ + 3/
C2 = 1/ + 2/ + 3/
C

1 0 0 1 1
0

0
0

1 0 0 1 1 0 0
0 1 0 0 1 1 0 0
0 0 1 0 0 1 1 0 0
0 0 1 0 0 1 1 0 0
1 0 1 1 1 1 1
1 1 1 1 0 0 1

11 01 11 11 10 10 11

Trong bảng 5.5 sau khi bổ xung hai bit đuôi vào chuỗi bit vào của bộ lập mã, thực
hiện trễ một bit (dịch toàn bộ chuỗi sang phải một bit), trễ hai bit (dịch chuỗi sang phải hai
bit) và trễ ba bit (dịch toàn bộ chuỗi sang phải ba bit). Sau đó cộng 1/ với 3/ (tương ứng với
g1,1 =1, g2,1 = 0 và g3,1 = 1) để được c1 và 1/ với 2/ và với 3/ (tương ứng với g1,2 = 1, g2,2 =
1, g3,2 =1) để được c2.

-361-


Phụ lục
Phụ lục 5C

GIẢI THUẬT MAP
1. Rút ra công thức tổng quát cho hàm LLR
Tại đầu vào bộ giải mã ta nhận được chuỗi N bit mã hóa, điều chế BPSK bị tạp âm
như sau:
R1,N = (R1,R2,…RN)

(5C.1)

trong đó Rk = (xk, yk), k=1, 2, 3,….N
Giả sử nkx và nky là hai biến ngẫu nhiên Gausơ trung bình không phương sai δ2 tương
ứng với tạp âm Gausơ trắng trong hai kênh, và dk là bit đầu vào bộ mã hóa và c k bit được
mã hóa tại thời điểm k. Ta được:
x k = a k + n kx

(5C.2)


y k = b k + n ky

(5C.3)

trong đó: a k = (1 − 2d k ) là ký hiệu của bit không mã hóa (thông tin hệ thống);
b k = (1 − 2c k ) là ký hiệu của bit được mã hóa (số liệu kiểm tra chẵn lẻ); k=1,2,3…N
Mục đích của giải mã MAP là tìm ra ước tính dˆ k có xác suất cao nhất khi cho trước
R1,N. Điều này đạt được bằng cách tính log hàm khả năng giống (LLR: Log Likelihood
Ratio) cho từng dk, hàm này được định nghĩa như sau:
 P ( d k = 0 | R1,N ) 
L dˆ k = ln 

 P ( d k = 1| R1,N ) 



( )

(5C.4)

Giá trị này được gọi là đầu ra mềm. Thực hiện quyết định cứng cho đầu ra này, ta có
thể xác định được bit thông tin có khả năng giống bit phát nhất:
NÕu L ( d k ) ≥ 0 ⇒ dˆ k = 0

(5C.5)

NÕu L ( d k ) < 0 ⇒ dˆ k = 1

Nếu Sk là trạng thái của bộ giải mã tại thời điểm k, ta được:
P ( d k = 0 | R1,N ) = ∑ P ( d k = 0,Sk = m | R1,N )


(5C.6)

m

Tương tự
P ( d k = 1| R1,N ) = ∑ P ( d k = 1,Sk = m | R1,N )

(5C.7)

m

trong đó m = 0,1… 2M − 1 , M là hằng số phần tử nhớ.
Ta đặt λ k ,i ( m ) = P ( d k = i,Sk = m | R1,N ) với i=0 hoặc 1 và cộng tất cả các trạng thái có
thể có của bộ giải mã, ta được:
 ∑ λ k,0 ( m ) 

ˆ
L d k = ln  m
 ∑ λ (m) 
 m k ,1


( )

(5C.8)

-362-



Phụ lục

trong đó λ k ,i ( m ) = P ( d k = i,Sk = m | R1,N ) là xác suất mà tại thời điểm k, trạng thái của bộ
giải mã là Sk = m bit phát bằng i khi cho trước chuỗi ký hiệu thu R1,N . Với biểu diễn
R1,N =  R1,k −1 , R k , R k +1,N  , trong đó R1,k-1 và Rk+1,N ký hiệu cho các ký hiệu từ R1 đến Rk-1và
các ký hiệu từ Rk+1 đến RN, ta có thể viết lại λ k,i ( m ) vào dạng sau:


λ k ,i ( m ) = P  d k = i,s k = m R1,k −1 R k R k +1,N 


C
A
B
D



(5C.9)

Sử dụng quy tắc Bayes sau đây
P ( A | B, C, D ) =
=

P ( A, B, C, D )
P ( B, C, D )

=

P ( B | A, C, D ) P ( A, C, D )

P ( B, C, D )

P ( B | A, C, D ) .P ( D | A, C ) P ( A, C )
P ( B, C, D )

Ta viết lại (5C.9) như sau

(

)

λ k ,i ( m ) = P R1,k −1 d k = i,s k = m, R k , R k +1,N .P ( R k +1,N d k = i,s k = m, R k )
× P ( d k = i,s k = m, R k ) P ( R1,N )

(5C.10)

trong đó R1,k-1, Rk+1,N ký hiệu cho chuỗi ký hiệu từ 1 đến k-1 và từ k+1 đến N tương ứng.
Do đó R1,k-1 chỉ liên quan đến trạng thái m mà nó gây ra và không phụ thuộc vào dk
cũng như Rk+1,N (là các sự kiện xẩy ra sau đó), nên thành phần thứ nhất trong tử số của
phương trình (5C.10) được viết lại và ký hiệu như sau:
P ( R1,k −1 | d k = i,Sk = m, R k , R k +1,N ) = P ( R 1,k −1 | Sk = m ) = α k ( m )

(5C.11)

α k ( m ) được gọi là số đo trạng thái thuận (Forward State Metric), biểu diễn xác suất chuỗi

ký hiệu thu trước thời điểm k và phụ thuộc vào trạng thái m tại thời điểm hiện thời k.
Sử dụng các phương trình trên cùng với việc suy luận Rk+1,N chỉ liên quan đến giá trị
bit dk và trạng thái tại thời điểm k (Sk=m) mà không phụ thuộc vào Rk (là các sự kiện xảy
ra trước đó), ta có thể biểu diễn thành phần thứ hai tử số của phương trình (5C.10) và ký

hiệu như sau:
P ( R k +1,N | d k = i,Sk = m, R k ) = P ( R k +1,N | d k = i,Sk = m )
P ( R k +1,N | Sk +1 = f ( i, m ) )

= βk +1,i ( f ( i, m ) )

(5C.12)

trong đó f ( i, m ) là trạng thái tiếp sau khi cho trước bit i và trạng thái m tại thời điểm k
βk +1,i ( f ( i, m ) ) được gọi là số đo trạng thái ngược (Backward State Metric). Nó biểu diễn

xác suất thu chuỗi ký hiệu sai thời điểm k và phụ thuộc vào trạng thái m cũng như bit trước
đó (tại thời điểm k). Sự kiện liên hiệp (dk=1, Sk=m) trong phương trình (5C.12) xác định
trạng thái tại thời điểm k: Sk+1.
Ta có thể biểu diễn thành phần thứ ba trong tử số của phương trình (5C.10) như sau:
P ( d k = i,Sk = m, R k ) = δk,i ( m )

(5C.13)

-363-


Phụ lục
δk,i ( m ) được gọi là số đo nhánh (Branch Metric) nó biểu diễn xác suất liên hiệp phát dk tại

trạng thái m và thu ký hiệu Rk. Số đo này phụ thuộc vào kênh truyền dẫn (Rk)
Sử dụng các phương trình (5C.11), (5C.12), (5C.13) ta được phương trình sau:
λ k ,i ( m ) =

α k ( m ) δk,i ( m ) βk +1,i ( m )

P ( R1,N )

(5C.14)

Sử dụng phương trình (5C.14) ta viết lại phương trình (5C.8) như sau:
 ∑ α k ( m ) δ k,0 ( m ) βk +1,0 ( f ( i, m ) ) 
⌢

L d k = ln  m
α
m
δ
m
β
f
i,
m
m
(
)
(
)
(
)
) 
k
k,1
k +1,1 (
 ∑
m



( )

(5C.15)

2. Biểu diễn số đo nhánh δk,i ( m )
Ta viết lại phương trình (5C.13) dựa trên nguyên tắc Bayes như sau:
δk,i ( m ) = P ( d k = i,Sk = m, R k )

= P ( R k | d k = i,Sk = m ) P ( d k = i,Sk = m )

(5C.15)

= P ( R k | d k = i,Sk = m ) P ( Sk = m | d k = i ) P ( d k = i )

Trạng thái thời điểm k không phụ thuộc vào số liệu đầu vào, nên:
P ( Sk = m | d k = i ) =

1
2M

(5C.16)

Coi kênh là AWGN có trung bình không, phương sai σ2 , ký hiệu P ( d k = i ) = γ k,1 và
tính toán xác suất từ các hàm mật độ xác suất khi dx → 0 và dy → 0 ta viết lại phương trình
(5C.15) như sau:
δk,i ( m ) =

 1  x k − a k ,i  2 

exp  − 
  dx k
δ
2
2πσ
 
 

γ k ,i
2M

 1  y − b ( m ) 2 
1
k,i

×
exp −  k
  dy k
δ
2πσ
 2 
 

(5C.17)

Lưu ý rằng, biểu diễn b là bk,i(m) để nhấn mạnh nó phụ thuộc vào bit đầu vào và
trạng thái m. Đơn giản hóa phương trình (5C.17) bằng cách loại bỏ các thành phần không
phụ thuộc vào i và m, ta được:
 x a + y k b k,i ( m ) 
δk,i ( m ) = γ k,i exp  k k ,i


σ2



(5C.18a)

Thay ak=1-2dk, bk=1-2ck và dk=i vào (5C.17) và loại bỏ thông tin không phụ thuộc
vào i và m ta được:
 x i + y k c k,i ( m ) 
δk,i ( m ) = γ k,i exp  − k

σ2 / 2



Hình 5C1 minh họa δk,i (m) trên biểu đồ dưới

-364-

(5C.18b)


Phụ lục

δ2,0 (00)

δ2,1 (01)
δ3,1 (00)


δ2,1 (10)
δ2,0 (01)
δ2,0 (10)

δ 2,1 (11)

Hình 5C1. Thể hiện δk,i ( m ) trên dưới

Nếu ta xét thí dụ cho hai nhánh trên hình 5C.1, sử dụng các phương trình (5C.18a),
(5C.2), (5C.3) với coi rằng γ k ,i = 1/ 2 và σ2 = 1 ta được:
δ 2,0 ( 00 ) =

1
exp {x 2 ×1 + y 2 × c 2,0 ( 00 )}
2

Và δ3,1 ( 00 ) = exp {x 3 × ( −1) + y3 × c3,1 ( 00 )}
1
2

3. Tính toán số đo trạng thái thuận α k ( m )

Biểu thức α k ( m ) được gọi là số đo trạng thái thuận và nó biểu diễn số đo trạng thái
cho chuyển đổi từ trạng thái m’ tại thời điểm k-1 sang trạng thái m tiếp theo tại thởi điểm k.
Từ phương trình (5C.11) ta biểu diễn α k ( m ) là tổng tất cả xác suất chuyển đổi trạng thái
m’ có thể xảy ra từ thời điểm k-1 dẫn đến trạng thái m tại thời điểm k ra như sau:
1

α k ( m ) = ∑∑ P ( d k −1 = j,Sk −1 = m ', R1,k −1 | Sk = m )


(5C.19)

m ' j= 0

Biểu diễn R1,k-1 thông qua [R1,k-2, Rk-1] và sử dụng quy tắc Bayes, phương trình
(5C.19) được viết lại như sau
α k ( m ) = ∑∑ P ( R1,k − 2 | Sk = m, d k −1 = j,Sk −1 = m ', R k −1 )
1

m ' j= 0

× P ( d k −1 = j,Sk −1 = m ', R k −1 | Sk = m )

α k ( m ) = ∑ P ( R1,k − 2 | Sk −1 = b j (m) ) P ( d k −1 = j,Sk −1 = b j (m), R k −1 )
1

(5C.20)

j= 0

trong đó bj(m) biểu thị trạng thái trước k chuyển vào trạng thái m khi bit đầu vào là j.

-365-


Phụ lục

Sử dụng (5C.13), phương trình (5C.20) được viết lại như sau:
α k ( m ) = ∑ α k −1 ( b j (m) ) δ k −1, j ( b j (m) )
1


(5C.21)

j= 0

trong đó bj(m) biểu thị trạng thái tại thời điểm k-1 chuyển vào trạng thái m tại thời điểm k
dưới tác động của bit dk-1= j.
Ta sẽ sử dụng lưới trên hình 5C.2 để giải thích công thức (5C.21).

( x k −1 , yk −1 )

( x k , yk )

α k (00) =  α k −1 (00)δk −1,0 (00) + α k −1 (01)δ k −1,1 (01) 
α k +1 (10) =  α k (01)δk,0 (01) + α k (00)δk,1 (00) 

Hình 5C2. Trình bày βk ( m ) trên dưới

Tất cả các α k ( m ) có thể được tính theo (5C.21) trong điều kiện chúng được khởi tạo
đúng, ta khởi tạo chúng như sau:
α1 ( 00 ) = 1& α1 ( m ≠ 0 ) = 0

(5C.22)

Để minh họa ta tính toán α 2 (00) xét điều kiện khởi đầu (5C.22) cho các minh họa
treo trên hình 5C.2:
α 2 ( 00 ) = α1 ( 00 ) δ1,0 ( 00 ) + α1 ( 01) δ1,1 ( 01)  = δ1,0 ( 00 )

4. Tính toán số đo trạng thái ngược βk ( m )


Biểu thức βk ( m ) rất giống biểu thức α k ( m ) . Thay vì tính tất cả β thuận theo thời
gian, ta tính toán chúng ngược theo thời gian. Chính vì thế chúng được gọi là các số đo
trạng thái ngược.
Từ phương trình (5C.12) ta có: βk −1 ( f ( i, m ) ) = P ( R k +1,N | Sk +1 = f ( i, m ) ) . Vậy:
βk ( m ) = P ( R k | Sk = m ) = P ( R k , R N,k +1 | Sk = m )

(5C.23)

Ta biểu diễn βk ( m ) là tổng tất cả các xác suất chuyển đổi trạng thái m có thể có đến
trạng thái m’ tại thời điểm k+1 như sau:

-366-


Phụ lục
βk ( m ) = ∑∑ P ( d k = j,Sk +1 = m ', R k, R k +1,N | Sk = m )
1

(5C.24)

m ' j= 0

Áp dụng quy tắc Bayes, ta được:
βk ( m ) = ∑∑ P ( R k +1,N | Sk = m, d k = j,Sk +1 = m ' )
1

m ' j= 0

(5C.25)


× P ( d k = j,Sk +1 = m ', R k | Sk = m )

Sk=m, dk=j hoàn toàn xác định trạng thái dẫn đến Sk+1=m’=f(j,m) (trạng thái tiếp sau xuất
phát từ m) khi cho trước đầu vào j và m, nên trong thành phần thứ hai của phương trình
(5C.25) ta có thể thay Sk+1=m’ bằng Sk=m và viết lại phương trình (5C.25) như sau:
βk ( m ) = ∑ P ( R k +1,N | Sk +1 = f ( i, m ) )P ( d k = j,Sk = m, R k )
1

j= 0

(5C.26)

1

= ∑ δ k , j ( m ) βk +1, j ( f ( j, m ) )
j= 0

Ta sẽ sử dụng lưới trên hình 5C3 để giải thích βk ( m )

( x k , yk )

( x k +1 , y k +1 )

βk (01) = βk +1,0 (00)δ k,0 (01) + βk +1,1 (10)δ k,1 (01)

Hình 5C3. Trình bày βk ,i ( m ) trên dưới

Phân tích hai nhánh tô đậm trên hình 4.24 ta thấy từ trạng thái m=10 tại thời điểm tk
sẽ có hai nhánh tiến tới hai trạng thái tại tk+1 như sau: trạng thái fk+1,0(m)=00 khi bit vào j=0
và trạng thái fk+1,1(m)=10 khi bit vào j=1. Vì vậy số đo ngược trong trường hợp này sẽ là:

βk ( 01) = βk +1,0 ( 00 ) δk,0 ( 01) + βk +1,1 (10 ) δk,1 ( 01)

Tất cả các giá trị β tính theo (5C.26) trong điều kiện chúng được khởi đầu ngược
đúng, hồi quy ngược được khởi đầu bằng cách buộc trạng thái cuối cùng trở về 0 và đặt:
βL + M +1 ( m = 0 ) = 1 vµ βL + M +1 ( m ≠ 0 ) = 0 `

-367-

(5C.27)


Phụ lục

trong đó L là số bit bản tin, M là số bit đuôi bằng không để phân cách các bản tin và bằng
số phần tử nhớ của thanh ghi dịch.
Dưới đây ta xét thí dụ minh họa tính toán βk,i ( 01) tại k=L+M với sử dụng điều kiện
khởi đầu ngược theo (5C.27) xét cho hình 5C3:
βL + M (01) = βL + M +1,0 ( 00 ) δk,0 ( 01)

Trường hợp L=1 và M=2 ta được:
β3 ( 01) = β4,0 ( 00 ) δ3,0 ( 01)
= δ3,0 ( 01)

Sau tất cả các định nghĩa trên ta có thể đi đến xét giải thuật cụ thể.

-368-