Slide bài giảng môn Lý thuyết thông tin nội dung chương 4: Truyền dẫn dữ liệu - Phần 1: Mã khối tuyến tính

Slide bài giảng môn Lý thuyết thông tin nội dung chương 4: Truyền dẫn dữ liệu - Phần 1: Mã khối tuyến tính của Học viện Công nghệ Bưu chính Viễn thông với những kiến thức và thông tin bổ ích giúp sinh viên tham khảo, ôn luyện và phục vụ nhu cầu học tập của mình cụ thể là có định hướng ôn tập, nắm vững kiến thức môn học và làm bài tốt trong những bài kiểm tra, bài tiểu luận, bài tập kết thúc học phần, từ đó học tập tốt và có kết quả cao cũng như có thể vận dụng tốt những kiến thức mình đã học vào thực tiễn cuộc sống. Mời bạn đọc đón xem!

lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
Biên soạn: Phạm
Mục tiêu của
bài học
Notes
T
r
a
n
g
bị một số khái niệm bản v hóa kênh
khối tuyến tính
vòng tuyến tính
2/30
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối
tuyến tính)
thuyết thông tin
Biên soạn: Phạm Văn Sự
Bộ môn Xử tín hiệu Truyền thông
Khoa Kỹ thuật Điện tử I
Học viện Công nghệ Bưu chính Viễn thông
ver. 22a
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
Các câu hỏi cần trả lời
Các tham số đánh giá hóa kênh?
Khoảng cách Hamming tối thiểu? vai trò trong việc đánh giá khả
năng phát hiện lỗi sửa lỗi của bộ mã?
khối tuyến tính? Ma trận sinh ma trận kiểm tra của khối tuyến
tính? khối tuyến tính hệ thống? Bài toán thiết kế mã khối tuyến tính?
vòng (mã cyclic, xyclic) tuyến tính? Đa thức sinh đa thức kiểm tra
của vòng tuyến tính? vòng tuyến tính hệ thống?
Biên soạn: Phạm Văn Sự (PTIT) C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính) ver. 22a 3/30
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1)
Notes
Nội dung chính
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
khối tuyến tính
khối tuyến tính
khối tuyến tính dạng hệ thống
Đánh giá khối nhị phân tuyến tính trên kênh BSC
Các vấn đề khi thiết kế khối tuyến tính
Kết thúc
4/30
1
2
3
4
5
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
Một số định nga khái niệm cơ bản
hóa khối
Encoder
k symbols
l-symbol block
Uncoded data stream
Coded data stream
Hình:
Quá trình a khối
Biên soạn: Phạm Văn S (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khi tuyến tính)
ver. 22a
5
/
30
Một số định nghĩa khái niệm bản
Notes
Véc-tơ
Định nghĩa (Véc-tơ mã)
Một bộ C = {c
0
, c
1
,...,c
M
1
} chứa các từ mã độ dài l, mỗi từ c
k
= (c
k
,
0,
c
k
,
1,..., c
k
,
l
1) với các dấu c
k
,
i
GF(q) (i = 0, l 1). C: bộ số q c
k
được
gọi từ mã, c-tơ M số t của bộ C.
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
Khối thông tin đầu vào tập {m
i
}, trong đó m
i
= (m
i
,
0
, m
i
,
1
,..., m
i
,
k
1
) với m
i
,
j
GF(q). Tập {m
i
} tạo
thành một không gian véc-tơ trên GF(q).
Nếu các khối thông tin cùng độ dài k thì số từ của bộ C phải thỏa mãn
M = q
k
.
Nếu các khối tin độ dài thay đổi thì M không dạng trên.
Các b hóa loại này khó thực thi hơn.
6/30
Một số định nga khái niệm cơ bản
Độ thừa mã, Tỷ số mã, Trọng số
Định nghĩa thừa của b mã)
Độ thừa của bộ mã
C
đưc định nghĩa
r
=
l
log
q
(
M
)
.
Nếu
M
=
2
k
thì
r
=
l
k
.
Định nghĩa (T số a)
Tỷ s mã hóa
R
đưc định nghĩa:
R
=
log
q
(
M
)
l
Nếu
M
=
2
k
thì
R
=
k
/
l
Định nghĩa (Trọng số của t mã/cấu tc lỗi)
Trọng số ca mt t mã
c
hoc ca một cu trúc lỗi
e
số du mã khác
0
trong
c
hoặc
e
. hiệu là
w
(
c
)
hoặc
w
(
e
)
0
w
(
c
)
l
Biên soạn: Phạm Văn S (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khi tuyến tính)
ver. 22a
7
/
30
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
min
=
d
0
=
min
c
1
,
c
2
C
,
c
1
=
c
2
d
(
c
1
,
c
2
)
Một số định nghĩa khái niệm bản
Notes
Khoảng cách Hamming
Định nghĩa (Khoảng cách mã Hamming)
Khoảng cách Hamming giữa hai từ c
1
c
2
tổng số vị trí tương ứng trong hai từ
dấu khác nhau.
d
Hamming
(c1, c2) = d(c1, c2) = |{i|c1
,
i
= c2
,
i
, i = 0, 1,..., l 1}|
d(c
1
, c
2
) = d(c
2
, c
1
).
0 d(c
1
, c
2
) l. d(c
1
, c
2
) + d(c
2
, c
3
) d(c
1
, c
3
) (Bất đẳng thức
tam giác).
Định nghĩa (Khoảng cách Hamming tối thiểu)
Khoảng cách mã tối thiểu, hay khoảng cách Hamming tối thiểu của một bộ khối C
khoảng cách Hamming tối thiểu giữa tất cả các cặp từ phân biệt trong bộ mã.
d
8/30
Một số định nghĩa khái niệm bản
Khả năng phát hiện sửa lỗi của
Định (Khả năng phát hiện lỗi của bộ mã)
Một bộ khoảng cách tối thiểu d
min
khả năng phát hiện tất cả các cấu
trúc lỗi trọng nhỏ hơn hoặc bằng (d
min
1).
Chú ý: Một số bộ thể phát hiện được các cấu trúc lỗi trọng d
min
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
2
3
Định (Khả năng sủa lỗi của bộ mã)
Một bộ khoảng cách tối thiểu d
min
kh năng sửa được tất cả c cấu
trúc lỗi trọng nhỏ hơn hoặc bằng
d
min
2
1
a
.
a
x phần nguyên lớn nhất nhỏ hơn hoặc
bằng x
Chú ý: Một số bộ thể sửa được c cấu trúc lỗi trọng
d
min
2
1
+ 1 hoặc
lớn hơn.
Biên soạn: Phạm Văn Sự (PTIT) C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính) ver. 22a 9/30
Một số định nghĩa khái niệm bản
Notes
r = c + e: véc-tơ thu.
Nếu không lỗi thì véc-tơ thu một từ hợp lệ.
Định dạng điều
chế, mức
hình truyền dẫn trong kênh nhiễu
c: từ phát, e: cấu trúc lỗi,
e=(e0,e1,...,el-1)
Hình: hình kênh nhiễu cộng
phát, mức nhiễu trên kênh quyết
định xảy ra một cấu trúc lỗi trong
+
c=(c0, c1, ..., cl-1)
r=(r0,r1,...,rl-1)
Channel
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
công suất q
l
cấu trúc lỗi thể. Máy thu thực hiện việc xem xét véc-tơ thu có phải từ
hợp lệ hay không: quá trình phát hiện lỗi. Khi máy thu phát hiện lỗi:
1
Yêu cầu phát lại: thông qua ARQ
HOẶC Đánh dấu từ mã lỗi: với các ng dụng real-time (voice, video,...) HOẶC Sửa
lỗi: FEC.
10/30
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1)
Nội dung chính
Các định nghĩa khái niệm bản
khối tuyến tính
khối tuyến tính
khối tuyến tính dạng hệ thống
Đánh giá khối nhị phân tuyến tính trên kênh BSC
Các vấn đề khi thiết kế khối tuyến tính
Kết thúc
1
2
3
4
5
lOMoARcPSD|3 6067889
Notes
Biên son: Phm Văn S (PTIT)
C4: Mã hóa kênh - Truyn dn d liu (Part 1: Mã khi tuyến tính)
ver. 22a
Biên soạn: Phạm Văn Sự (PTIT) C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính) ver. 22a 11/30
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1)
Notes
Nội dung chính
Các định nghĩa khái niệm bản
khối tuyến tính
khối tuyến tính
khối tuyến tính dạng hệ thống
Đánh giá khối nhị phân tuyến tính trên kênh BSC
Các vấn đề khi thiết kế khối tuyến tính
Kết thúc
12/30
khối tuyến tính
Định nghĩa
Định nghĩa (Mã khối tuyến tính)
Xét một bộ khối C gồm các từ độ dài l {c
k
= (c
k
,
0
, c
k
,
1
,..., c
k
,
l
1
)} với các dấu
thuộc GF(q). Bộ C một bộ khối tuyến tính cơ số q nếu chỉ nếu C tạo
thành một không gian véc-tơ con trên GF(q).
1
2
3
4
5
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
Định nghĩa (Chiều của một bộ khối)
Chiều của một bộ khối chiều của không gian véc-tơ tương ứng.
hiệu: C(l, k) hoặc C(l, k, d
0
).
1 Tổ hợp tuyến tính của một tập các từ bất kỳ một từ C luôn chứa từ
toàn 0
2 Khoảng cách mã tối thiểu của bộ khối tuyến tính bằng trọng số của một từ
trọng số nhỏ nhất khác từ toàn không.
3 Các cấu trúc lỗi không thể phát hiện được của bộ độc lập với từ mã phát
luôn chứa tập tất cả các từ không toàn 0.
Biên soạn: Phạm Văn Sự (PTIT) C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính) ver. 22a 13/30
khối tuyến tính
Notes
Ma trận sinh của khối tuyến tính
Gọi {g
0
, g
1
,...,g
k
1
} sở của các từ trong bộ C(l, k).
Ma trận sinh G(k × l)của bộ được thành lập như sau:
g
0
g0
,
,0 g0,,1 ... g
G = ...g1 = g1... 0, g1... 1,
gk1 gk1 0 gk1 1 ... gk
Gọi a = (a
0
, a
1
,..., a
k
1
) khối dữ liệu đầu vào (bản tin) cần hóa.
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
Từ thu được t phép mã hóa:
c = aG = [a0, a1,..., a
k
1]G
= a0g0 + a1g1 + ··· + a
k
1g
k
1
14/30
khi tuyến tính
Ma trận kiểm tra tính chẵn lẻ
Với
C
, tồn tại
C
kng gian véc-tơ đối ngẫu
(
l
k
)
chiều.
Gọi
{
h
0
,
h
1
,...,
h
l
k
1
}
sở ca
C
.
Ma trận sinh H
(
l
k
×
l
)
của
C
:
H
=
h
0
h
1
...
h
l
k
1
=
h
0
,
0
h
0
,
1
...
h
0
,
l
1
h
1
,
0
h
1
,
1
...
h
1
,
l
1
.
.
.
.
.
.
.
.
.
.
.
.
h
l
k
1
,
0
h
l
k
1
,
1
...
h
l
k
1
,
l
1
H ma trận kiểm tra chn lẻ của mã
C
GH
T
=
0.
Định
Một véc-tơ
c
một t thuộc
C
nếu và ch nếu
cH
T
=
0
cH
T
=
0
gọi biểu thức kiểm tra chẵn lẻ.
Biên soạn: Phạm Văn S (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khi tuyến tính)
ver. 22a
15
/
30
khối tuyến tính
Notes
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
Ma trận kiểm tra tính chẵn lẻ khoảng cách
Định
Giả sử bộ C ma trận kiểm tra tính chẵn lẻ H. Khoảng cách tối thiểu của bộ
C bằng số cột tối thiểu khác 0 của H tổ hợp tuyến tính không tầm thường của
chúng bằng 0.
Định (Giới hạn Singleton)
Với bộ khối tuyến tính C(l, k), khoảng cách tối thiểu thỏa mãn bất đẳng thức:
d
min
l k + 1
16/30
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1)
Nội dung chính
Các định nghĩa khái niệm bản
khối tuyến tính
khối tuyến tính
khối tuyến tính dạng hệ thống
Đánh giá khối nhị phân tuyến tính trên kênh BSC
Các vấn đề khi thiết kế khối tuyến tính
Kết thúc
1
2
3
4
5
Biên soạn: Phạm Văn Sự (PTIT) C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính) ver. 22a 17/30
khối tuyến tính
Notes
khối tuyến tính hệ thống
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
H
=
I
l
k
|
P
T
Định nghĩa (Mã khối tuyến tính hệ thống)
khối tuyến tính hệ thống C(l, k) thực hiện việc ánh xạ bản tin (khối dữ liệu) độ dài
k thành một c-tơ/từ đ dài l sao cho trong số l bít thể chỉ ra k t bản tin
số còn lại l k bít kiểm tra tính chẵn lẻ.
Giả sử từ mã xây dựng có dạng c = [p
1
| a]
a: khối thông tin (bản tin) đ dài k; p
1
: khối bít kiểm tra đ dài l k
G phương pháp khử Gausse−→
G
P
(k
×
l
k)
: ma trận tạo dấu kiểm tra
I
(k
×
k)
: ma trận đơn vị.
GH
T
= 0
18/30
Chý ý
:
Nếu xét c
= [
a
|
p
1
]
G
=
I
k
|
P
H
=
P
T
|
I
l
k
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1)
Nội dung chính
Các định nghĩa khái niệm bản
khối tuyến tính
khối tuyến tính
khối tuyến tính dạng hệ thống
Đánh giá khối nhị phân tuyến tính trên kênh BSC
Các vấn đề khi thiết kế khối tuyến tính
Kết thúc
1
2
3
4
5
Biên soạn: Phạm Văn Sự (PTIT) C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính) ver. 22a 19/30
Đánh giá khối nhị phân tuyến tính trên kênh BSC
Notes
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
dụ
dụ
Xét bộ nhị phân đều chiều dài l (ví dụ bộ mã nhị phân đều chiều dài 2: C = (00),
(01), (11), (10)). Giả s kết quả mã hóa được truyền qua kênh nhị phân rời rạc đối
xứng không nh (BSC) xác suất thu sai p
0
, các bít được phát đi độc lập nhau,
xác suất phát đi bít 0 bít 1 tương đương nhau.
1 Tính xác suất thu được một từ đúng.
2 Giả sử xác suất sai cho phép đối với việc thu các từ p
a
, tìm điều kiện đối
với p
0
để thể sử dụng được bộ cho việc thông tin qua kênh.
20/30
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
Biên soạn: Phạm Văn Sự
(PTIT)C4: hóa kênh - Truyền dẫn dữ
liệu (Part 1: khối tuyến tính) ver. 22a 21/30
Đánh giá
khối nhị phân
tuyến tính
trên kênh BSC
Notes
Đánh giá khả năng phát
hiện lỗi (cont.)
P
u
b
: tỷ lệ bít lỗi không được phát hiện
xác suất bít thông tin nhận được bị lỗi trong một từ b tác động bởi cấu trúc lỗi
không phát hiện được
Pu
P
d
b
: tỷ lệ bít lỗi được phát hiện
xác suất bít thông tin nhận được bị lỗi trong một từ b tác động bởi cấu trúc lỗi
thể phát hiện được.
Pd
Nếu biết phân bố trọng của bộ mã, P
u
b
thể tính một cách chính xác:
Pu =p
(
Đánh giá khối nhị phân tuyến tính trên kênh BSC
Đánh giá khả năng phát hiện lỗi
Cho C(l, k, d
min
) truyền qua kênh BSC xác suất chuyển sai p.
P
u
(E): xác suất véc-tơ thu lỗi không phát hiện được.
P
e
(E): xác suất véc-tơ thu lỗi.
P
d
(E): xác suất véc-
thu lỗi được
phát hiện.
l
Pu(E)
j=d
min
l
Pu(E) = X Ajpj(1 p)lj
j=d
min
l
P
e
(E) = Xp
j
(1 p)
lj
= 1 (1 p)
l
j=1
P
d
(E) = P
e
(E) P
u
(E) = 1 (1 p)
l
P
u
(E)
X
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
k j=d
min
trong đó B
j
tổng trọng của các khối tin tương ứng với tất cả các từ
trọng i.
22/30
Đánh giá khối nhị phân tuyến tính trên kênh BSC
Đánh giá khả năng sửa lỗi
Cho
C
(
l
,
k
,
d
min
)
truyn qua kênh BSC có xác sut chuyn sai
p
.
t b giải mã có đ dài gii hạn.
P
(
E
)
:
xác suất giải mã sai
P
(
E
)
l
X
j
=
d
min
1
2
+
1
l
j
p
j
(
1
p
)
l
j
=
1
d
min
1
2
X
j
=
0
l
j
p
j
(
1
p
)
l
j
Đẳng thc xảy ra ch khi mã hoàn hảo.
P
(
F
)
:
xác suất giải mã thất bại
P
(
F
)
1
d
min
1
2
X
j
=
0
l
j
p
j
(
1
p
)
l
j
Biên soạn: Phạm Văn S (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khi tuyến tính)
30
/
23
ver. 22a
Đánh giá khối nhị phân tuyến tính trên kênh BSC
Notes
Đánh giá khả năng sửa lỗi (cont’)
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
Xét C(l, k, d
min
) với phân bố trọng số đã biết {A
i
}
P
k
j
xác suất một véc-tơ thu khoảng cách Hamming chính xác k so với một t
trọng j.
k
Pkj =
Xpjk+2r (1 p)lj+k2r
r=0
l
P(E) =
Xmin AjP
k
j
j=d
k=0
P p
j
(1 p)
lj
P(E)
24/30
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
Đánh giá khối nhị phân tuyến tính trên kênh BSC
Đánh giá khả năng sửa lỗi (cont’)
Nếu biết được mối quan hệ giữa trọng số của các khối tin và trọng s các từ
mã tương ng
B
j
BER
=
P
b
(
E
) =
1
k
l
X
j
=
d
min
B
j
d
min
1
2
X
k
=
0
P
j
k
Chú ý
:
Thường, thông tin
{
B
j
}
không
kh thi.
Chủ yếu dựa vào các đánh giá
biên
P
(
E
)
P
b
(
E
)
1
k
P
(
E
)
Biên soạn: Phạm Văn S (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khi tuyến tính)
/
30
ver. 22a
25
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1)
Notes
Nội dung chính
Các định nghĩa khái niệm bản
khối tuyến tính
1
2
3
4
5
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
khối tuyến tính dạng h thống
Đánh giá khối nhị phân tuyến nh trên kênh BSC
Các vấn đề khi thiết kế khối tuyến tính
Kết thúc
26/30
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
Các vấn đ khi thiết kế mã khối tuyến tính
Thiết kế khối tuyến tính tối ưu
Khi thiết kế, ta mong mun có được b mã có đ dư tha nh nht có thể, nhưng
lại khả năng phát hiện sửa lỗi lớn nhất thể
.
Trường hợp 1
Với
k
d
min
cho trước, xây dng bộ mã có đ dư tha tối thiu:
min
{
l
}
.
Độ dài từ của bộ mã thỏa n giới hạn Griesmer:
l
k
1
X
i
=
0
d
min
2
i
x
:
phần nguyên nh nhất lớn n hoặc bằng
x
.
Biên soạn: Phạm Văn S (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khi tuyến tính)
ver. 22a
27
/
30
Các vấn đề khi thiết kế khối tuyến tính
Notes
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
Thiết kế khối tuyến tính tối ưu (cont’)
Trường hợp 2
Với
l
k
cho trước, xây dựng bộ khả năng phát hiện và sửa sai lớn nhất:
max
{
d
min
}
.
Khong cách Hamming ti thiu ca b mã tha mãn giới hạn Plotkin:
d
min
l
×
2
k
1
2
k
1
Trường hợp 3
Với
l
kh ng sửa sai
t
cho trước, xây dng bộ mã có đ dư tha nhỏ nht:
max
{
k
}
.
Mối liên hệ giữa
l
,
k
t
tha mãn giới hn Hamming:
2
l
k
t
X
i
=
0
l
i
28
/
30
Biên soạn: Phạm Văn Sự (PTIT) C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính) ver. 22a 29/30
Notes
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1)
Nội dung chính
Các định nghĩa khái niệm bản
khối tuyến tính
khối tuyến tính
khối tuyến tính dạng h thống
Đánh giá khối nhị phân tuyến tính trên kênh BSC
Các vấn đề khi thiết kế khối tuyến tính
Kết thúc
1
2
3
4
5
lOMoARcPSD|3 6067889
Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: hóa kênh - Truyền dẫn dữ liệu (Part 1: khối tuyến tính)
ver. 22a
Kết thúc phần mã khối tuyến tính
30/30
| 1/24

Preview text:

lOMoARcPSD|36067889
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối Notes tuyến tính) Biên soạn: Phạm Lý thuyết thông tin Biên soạn: Phạm Văn Sự
Bộ môn Xử lý tín hiệu và Truyền thông Mục tiêu của
Khoa Kỹ thuật Điện tử I
Học viện Công nghệ Bưu chính Viễn thông bài học Notes ver. 22a T r a n g
bị một số khái niệm cơ bản về mã hóa kênh Mã khối tuyến tính Mã vòng tuyến tính 2/30
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes
Các câu hỏi cần trả lời
Các tham số đánh giá mã hóa kênh?
Khoảng cách mã Hamming tối thiểu? Có vai trò gì trong việc đánh giá khả
năng phát hiện lỗi và sửa lỗi của bộ mã?
Mã khối tuyến tính? Ma trận sinh và ma trận kiểm tra của mã khối tuyến
tính? Mã khối tuyến tính hệ thống? Bài toán thiết kế mã khối tuyến tính?
Mã vòng (mã cyclic, mã xyclic) tuyến tính? Đa thức sinh và đa thức kiểm tra
của mã vòng tuyến tính? Mã vòng tuyến tính hệ thống?
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a 3/30
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1) Notes Nội dung chính
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes 1
Các định nghĩa và khái niệm cơ bản 2 Mã khối tuyến tính Mã khối tuyến tính
Mã khối tuyến tính dạng hệ thống 3
Đánh giá mã khối nhị phân tuyến tính trên kênh BSC 4
Các vấn đề khi thiết kế mã khối tuyến tính 5 Kết thúc 4/30
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes
Một số định nghĩa và khái niệm cơ bản Mã hóa khối Uncoded data stream k symbols Encoder l-symbol block Coded data stream
Hình: Quá trình mã hóa khối
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a 5 /30
Một số định nghĩa và khái niệm cơ bản Notes Véc-tơ mã Định nghĩa (Véc-tơ mã)
Một bộ mã C = {c0, c1,. .,cM−1} chứa các từ mã có độ dài l, mỗi từ mã ck= (ck,0,
ck,1,. ., ck,l−1) với các dấu mã ck,i ∈ GF(q) (i = 0, l − 1). C: bộ mã cơ số q ck được
gọi là từ mã, véc-tơ mã M là số từ mã của bộ mã C.
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes
Khối thông tin đầu vào là tập {mi}, trong đó mi = (mi,0, mi,1,. ., mi,k−1) với mi,j ∈ GF(q). Tập {mi} tạo
thành một không gian véc-tơ trên GF(q).
Nếu các khối thông tin có cùng độ dài k thì số từ mã của bộ mã C phải thỏa mãn M = qk.
Nếu các khối tin có độ dài thay đổi thì M không có dạng trên.
▶ Các bộ mã hóa loại này khó thực thi hơn. 6/30
Một số định nghĩa và khái niệm cơ bản
Độ dư thừa mã, Tỷ số mã, Trọng số mã
Định nghĩa (Độ dư thừa của bộ mã)
Độ dư thừa của bộ mã C được định nghĩa là r = l − logq(M). Nếu M = 2k thì r = l − k.
Định nghĩa (Tỷ số mã hóa)
Tỷ số mã hóa R được định nghĩa: R = logq(M) l
Nếu M = 2k thì R = k/l
Định nghĩa (Trọng số của từ mã/cấu trúc lỗi)
Trọng số của một từ mã c hoặc của một cấu trúc lỗi e là số dấu mã khác 0 trong
c hoặc e. Kí hiệu là w(c) hoặc w(e) 0 ≤ w(c) ≤ l
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a 7 /30
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes
Một số định nghĩa và khái niệm cơ bản Notes Khoảng cách mã Hamming
Định nghĩa (Khoảng cách mã Hamming)
Khoảng cách Hamming giữa hai từ mã c1 và c2 là tổng số vị trí tương ứng trong hai từ mã mà dấu mã khác nhau.
dHamming (c1, c2) = d(c1, c2) = |{i|c1,i ̸= c2,i, i = 0, 1,. ., l − 1}|
d(c1, c2) = d(c2, c1).
0 ≤ d(c1, c2) ≤ l. d(c1, c2) + d(c2, c3) ≥ d(c1, c3) (Bất đẳng thức tam giác).
Định nghĩa (Khoảng cách Hamming tối thiểu)
Khoảng cách mã tối thiểu, hay khoảng cách Hamming tối thiểu của một bộ mã khối C
là khoảng cách Hamming tối thiểu giữa tất cả các cặp từ mã phân biệt trong bộ mã. d min = d0 = min d(c1, c2) ∀c1 c c , 2∈ C, 1̸=c2 8/30
Một số định nghĩa và khái niệm cơ bản
Khả năng phát hiện và sửa lỗi của mã
Định lý (Khả năng phát hiện lỗi của bộ mã)
Một bộ mã có khoảng cách mã tối thiểu dmin có khả năng phát hiện tất cả các cấu
trúc lỗi có trọng nhỏ hơn hoặc bằng (dmin − 1).
Chú ý: Một số bộ mã có thể phát hiện được các cấu trúc lỗi có trọng ≥ dmin
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes
Định lý (Khả năng sủa lỗi của bộ mã)
Một bộ mã có khoảng cách mã tối thiểu dmin có khả năng sửa được tất cả các cấu
trúc lỗi có trọng nhỏ hơn hoặc bằng ⌊dmin2−1⌋ a. a⌊x⌋ là phần nguyên lớn nhất nhỏ hơn hoặc bằng x
Chú ý: Một số bộ mã có thể sửa được các cấu trúc lỗi có trọng ⌊dmin2−1⌋ + 1 hoặc lớn hơn.
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a 9/30
Một số định nghĩa và khái niệm cơ bản
Mô hình mã truyền dẫn trong kênh có nhiễu
c: từ mã phát, e: cấu trúc lỗi, Channel + c=(c0, c1, . ., cl-1) r=(r0,r1,. .,rl-1) Notes r = c + e: véc-tơ thu.
▶ Nếu không có lỗi thì véc-tơ thu là một từ mã hợp lệ. Định dạng điều e=(e0,e1,. .,el-1)
phát, và mức nhiễu trên kênh quyết chế, mức
Hình: Mô hình kênh nhiễu cộng
định xảy ra một cấu trúc lỗi trong 2
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a 3 lOMoARcPSD|36067889 Notes
công suất ql cấu trúc lỗi có thể. Máy thu thực hiện việc xem xét véc-tơ thu có phải là từ mã
hợp lệ hay không: quá trình phát hiện lỗi. Khi máy thu phát hiện lỗi: 1
Yêu cầu phát lại: thông qua ARQ
HOẶC Đánh dấu từ mã lỗi: với các ứng dụng real-time (voice, video,. .) HOẶC Sửa lỗi: FEC. 10/30
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1) Nội dung chính 1
Các định nghĩa và khái niệm cơ bản 2 Mã khối tuyến tính Mã khối tuyến tính
Mã khối tuyến tính dạng hệ thống
Đánh giá mã khối nhị phân tuyến tính trên kênh BSC 3
Các vấn đề khi thiết kế mã khối tuyến tính 4 Kết thúc 5
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a 11/30
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1) Notes Nội dung chính 1
Các định nghĩa và khái niệm cơ bản 2 Mã khối tuyến tính Mã khối tuyến tính
Mã khối tuyến tính dạng hệ thống 3
Đánh giá mã khối nhị phân tuyến tính trên kênh BSC 4
Các vấn đề khi thiết kế mã khối tuyến tính 5 Kết thúc 12/30 Mã khối tuyến tính Định nghĩa
Định nghĩa (Mã khối tuyến tính)
Xét một bộ mã khối C gồm các từ mã độ dài l {ck = (ck,0, ck,1,. ., ck,l−1)} với các dấu mã
thuộc GF(q). Bộ mã C là một bộ mã khối tuyến tính cơ số q nếu và chỉ nếu C tạo
thành một không gian véc-tơ con trên GF(q).
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes
Định nghĩa (Chiều của một bộ mã khối)
Chiều của một bộ mã khối là chiều của không gian véc-tơ tương ứng.
Ký hiệu: C(l, k) hoặc C(l, k, d0). 1
Tổ hợp tuyến tính của một tập các từ mã bất kỳ là một từ mã ⇒ C luôn chứa từ mã toàn 0 2
Khoảng cách mã tối thiểu của bộ mã khối tuyến tính bằng trọng số của một từ
mã có trọng số nhỏ nhất khác từ mã toàn không. 3
Các cấu trúc lỗi không thể phát hiện được của bộ mã độc lập với từ mã phát và
luôn chứa tập tất cả các từ mã không toàn 0.
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a 13/30 Mã khối tuyến tính
Notes Ma trận sinh của mã khối tuyến tính
Gọi {g0, g1,. .,gk−1} là cơ sở của các từ mã trong bộ mã C(l, k).
Ma trận sinh G(k × l)của bộ mã được thành lập như sau: g0 g0, 0 g0, 1 . . g G = . .g1 =
g1. . 0, g1. . 1, gk−1 gk−1 0 gk−1 1 . . gk
Gọi a = (a0, a1,. ., ak−1) là khối dữ liệu đầu vào (bản tin) cần mã hóa.
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes
Từ mã thu được từ phép mã hóa: c =
aG = [a0, a1,. ., ak−1]G =
a0g0 + a1g1 + ··· + ak−1gk−1 14/30 Mã khối tuyến tính
Ma trận kiểm tra tính chẵn lẻ
Với C, tồn tại C⊥ là không gian véc-tơ đối ngẫu (l − k) chiều.
Gọi {h , h ,. ., h 0 1
l − k − 1 } là cơ sở của C⊥ . ⇒ Ma trận sinh H(l − k × l ) của C⊥ : h h0 0 h0 1 . . h0 0 , , ,l− 1 h . . h1 H h = 1 1 ,0 h1 ,1 ,l− 1 . . = .. . . . . .. .. .. hl− k− 1 hl− k− 1 0 h 1 . . h , l− k− 1, l− k− 1,l− 1
H là ma trận kiểm tra chẵn lẻ của mãC GHT = 0. Định lý
Một véc-tơ c là một từ mã thuộc C nếu và chỉ nếu cHT = 0
cHT = 0 gọi là biểu thức kiểm tra chẵn lẻ.
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a 15 /30 Mã khối tuyến tính Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes
Ma trận kiểm tra tính chẵn lẻ và khoảng cách mã Định lý
Giả sử bộ mã C có ma trận kiểm tra tính chẵn lẻ H. Khoảng cách mã tối thiểu của bộ
mã C bằng số cột tối thiểu khác 0 của H mà tổ hợp tuyến tính không tầm thường của chúng bằng 0.
Định lý (Giới hạn Singleton)
Với bộ mã khối tuyến tính C(l, k), khoảng cách mã tối thiểu thỏa mãn bất đẳng thức: dmin ≤ l − k + 1 16/30
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1) Nội dung chính 1
Các định nghĩa và khái niệm cơ bản 2 Mã khối tuyến tính Mã khối tuyến tính
Mã khối tuyến tính dạng hệ thống
Đánh giá mã khối nhị phân tuyến tính trên kênh BSC 3
Các vấn đề khi thiết kế mã khối tuyến tính 4 Kết thúc 5
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a 17/30 Mã khối tuyến tính Notes
Mã khối tuyến tính hệ thống
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes
Định nghĩa (Mã khối tuyến tính hệ thống)
Mã khối tuyến tính hệ thống C(l, k) thực hiện việc ánh xạ bản tin (khối dữ liệu) độ dài
k thành một véc-tơ/từ mã độ dài l sao cho trong số l bít có thể chỉ ra k bít bản tin và
số còn lại l − k bít kiểm tra tính chẵn lẻ.
Giả sử từ mã xây dựng mã có dạng c = [p1 | a]
a: khối thông tin (bản tin) độ dài k; p1: khối bít kiểm tra độ dài l − k
G phương pháp khử Gausse−→ G
Chý ý: Nếu xét c = [a | p1]
P(k×l−k): ma trận tạo dấu kiểm tra G = Ik | P I(k×k): ma trận đơn vị. ⇒ H = − PT | Il− k ⇒ H = Il− k | − PT ⇒ GHT = 0 18/30
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1) Nội dung chính 1
Các định nghĩa và khái niệm cơ bản 2 Mã khối tuyến tính Mã khối tuyến tính
Mã khối tuyến tính dạng hệ thống
Đánh giá mã khối nhị phân tuyến tính trên kênh BSC 3
Các vấn đề khi thiết kế mã khối tuyến tính 4 Kết thúc 5
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a 19/30
Đánh giá mã khối nhị phân tuyến tính trên kênh BSC Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes Ví dụ Ví dụ
Xét bộ mã nhị phân đều chiều dài l (ví dụ bộ mã nhị phân đều chiều dài 2: C = (00),
(01), (11), (10)). Giả sử kết quả mã hóa được truyền qua kênh nhị phân rời rạc đối
xứng không nhớ (BSC) có xác suất thu sai p0, các bít được phát đi độc lập nhau, và
xác suất phát đi bít 0 và bít 1 tương đương nhau. 1
Tính xác suất thu được một từ mã đúng. 2
Giả sử xác suất sai cho phép đối với việc thu các từ mã là pa, tìm điều kiện đối
với p0 để có thể sử dụng được bộ mã cho việc thông tin qua kênh. 20/30
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889
Đánh giá mã khối nhị phân tuyến tính trên kênh BSC
Đánh giá khả năng phát hiện lỗi Notes
Cho C(l, k, dmin) truyền qua kênh BSC có xác suất chuyển sai p.
Pu(E): xác suất véc-tơ thu có lỗi mà không phát hiện được. Biên soạn: Phạm Văn Sự
Pe(E): xác suất véc-tơ thu có lỗi.
(PTIT)C4: Mã hóa kênh - Truyền dẫn dữ Pd(E): xác suất véc-
tơ thu có lỗi được liệu(Part1:Mãkhốituyếntính) ver. 22a 21/30 phát hiện. l Pu(E) ≤ j=dmin Đánh giá mã l khối nhị phân Pu(E) = X Ajpj(1 − p)l−j tuyến tính trên kênh BSC Notes Đánh giá khả năng phát j=dmin l hiện lỗi (cont.) Pe(E)
= Xpj(1 − p)l−j = 1 − (1 − p)l j=1 P Pd(E) =
Pe(E) − Pu(E) = 1 − (1 − p)l − Pu(E) u
b : tỷ lệ bít lỗi không được phát hiện ▶ ≜
xác suất bít thông tin nhận được bị lỗi trong một từ mã bị tác động bởi cấu trúc lỗi không phát hiện được ▶ Pu
Pdb: tỷ lệ bít lỗi được phát hiện ▶ ≜
xác suất bít thông tin nhận được bị lỗi trong một từ mã bị tác động bởi cấu trúc lỗi có thể phát hiện được. ▶ Pd
Nếu biết phân bố trọng của bộ mã, Pubcó thể tính một cách chính xác: X Pu =p (
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes k j=dmin
trong đó Bj là tổng trọng của các khối tin tương ứng với tất cả các từ mã có trọng là i. 22/30
Đánh giá mã khối nhị phân tuyến tính trên kênh BSC
Đánh giá khả năng sửa lỗi
Cho C(l, k, d ) truyền qua kênh BSC có xác suất chuyển saip. min
Xét bộ giải mã có độ dài giới hạn.
P(E ): xác suất giải mã sai 1 l l ⌊ dmin− 2 ⌋ l P(E ) ≤ X pj(1 − p)l− j = 1 − X pj(1 − p)l− j 1 j j j=⌊ dmin− j=0 2 ⌋ +1
Đẳng thức xảy ra chỉ khi mã là hoàn hảo.
P(F ): xác suất giải mã thất bại 1 ⌊ dmin− 2 ⌋ l P(F ) ≤ 1 − X pj(1 j − p)l− j j=0
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a 23 /30
Đánh giá mã khối nhị phân tuyến tính trên kênh BSC Notes
Đánh giá khả năng sửa lỗi (cont’)
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes
Xét C(l, k, dmin) với phân bố trọng số đã biết {Ai}
P jk ≜ xác suất một véc-tơ thu có khoảng cách Hamming chính xác là k so với một từ mã có trọng là j. k Pkj =
Xpj−k+2r (1 − p)l−j+k−2r r=0 l P(E) = XminAjPkj j=d k=0 P pj(1 − p)l−j − P(E) 24/30
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes
Đánh giá mã khối nhị phân tuyến tính trên kênh BSC
Đánh giá khả năng sửa lỗi (cont’)
Nếu biết được mối quan hệ giữa trọng số của các khối tin và trọng số các từ mã tương ứng ▶ ⇒ Bj ⇒ 1 1 l ⌊ dmin− 2 ⌋ BER = Pb(E) = X B X Pj k j k j=dmin k=0
Chú ý: Thường, thông tin {B } không j khả thi.
⇒ Chủ yếu dựa vào các đánh giá biên 1 P(E ) ≥ P (E) ≥ P(E) b k
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a 25 /30
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1) Notes Nội dung chính 1
Các định nghĩa và khái niệm cơ bản 2 Mã khối tuyến tính Mã khối tuyến tính 3 4
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a 5 lOMoARcPSD|36067889 Notes
Mã khối tuyến tính dạng hệ thống
Đánh giá mã khối nhị phân tuyến tính trên kênh BSC
Các vấn đề khi thiết kế mã khối tuyến tính Kết thúc 26/30
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes
Các vấn đề khi thiết kế mã khối tuyến tính
Thiết kế mã khối tuyến tính tối ưu
Khi thiết kế, ta mong muốn có được bộ mã có độ dư thừa nhỏ nhất có thể, nhưng
lại có khả năng phát hiện và sửa lỗi lớn nhất có thể. Trường hợp 1
Với k và dmin cho trước, xây dựng bộ mã có độ dư thừa tối thiểu: min{l}.
Độ dài từ mã của bộ mã thỏa mãn giới hạn Griesmer: k− 1 d l ≥ X ⌈ min 2i ⌉ i=0
⌈x⌉: phần nguyên nhỏ nhất lớn hơn hoặc bằng x.
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a 27 /30
Các vấn đề khi thiết kế mã khối tuyến tính Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1)
Thiết kế mã khối tuyến tính tối ưu (cont’) Nội dung chính Trường hợp 2 Với 1
Các định nghĩa và khái niệm cơ bản
l và k cho trước, xây dựng bộ mã có khả năng phát hiện và sửa sai lớn nhất: max{dmin}.
Khoảng cách Hamming tối thiểu của bộ mã thỏa mãn giới hạn Plotkin: 2 Mã khối tuyến tính Mã khối tuyến tính l d × 2k− 1 min ≤ 2k
Mã khối tuyến tính dạng hệ thống − 1 Trường hợp 3
Đánh giá mã khối nhị phân tuyến tính trên kênh BSC 3
Với l và khả năng sửa sai t cho trước, xây dựng bộ mã có độ dư thừa nhỏ nhất:
Các vấn đề khi thiết kế mã khối tuyến tính max{k}. 4
Mối liên hệ giữa l, k và t thỏa mãn giới hạn Hamming: t Kết thúc 5 2l− k l ≥ X i i=0 28 /30
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a 29/30 Notes
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a lOMoARcPSD|36067889 Notes
Kết thúc phần mã khối tuyến tính 30/30
Biên soạn: Phạm Văn Sự (PTIT)
C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1: Mã khối tuyến tính) ver. 22a
Document Outline

  • Mục tiêu của bài học
  • C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1)
  • Một số định nghĩa và khái niệm cơ bản
    • Định nghĩa (Véc-tơ mã)
  • Một số định nghĩa và khái niệm cơ bản
    • Định nghĩa (Khoảng cách mã Hamming)
    • Định nghĩa (Khoảng cách Hamming tối thiểu)
  • Một số định nghĩa và khái niệm cơ bản
    • Định lý (Khả năng phát hiện lỗi của bộ mã)
    • Định lý (Khả năng sủa lỗi của bộ mã)
  • Một số định nghĩa và khái niệm cơ bản
  • C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1)
  • Mã khối tuyến tính
    • Định nghĩa (Mã khối tuyến tính)
    • Định nghĩa (Chiều của một bộ mã khối)
  • Mã khối tuyến tính
  • Mã khối tuyến tính
    • Định lý
    • Định lý (Giới hạn Singleton)
  • Mã khối tuyến tính
    • Định nghĩa (Mã khối tuyến tính hệ thống)
  • Đánh giá mã khối nhị phân tuyến tính trên kênh BSC
    • Ví dụ
  • Đánh giá mã khối nhị phân tuyến tính trên kênh BSC
  • Đánh giá mã khối nhị phân tuyến tính trên kênh BSC
  • C4: Mã hóa kênh - Truyền dẫn dữ liệu (Part 1)
  • Các vấn đề khi thiết kế mã khối tuyến tính