Vietebooks Nguyn Hong Cng
Trang 16

Đặc trng sau đây có khó hơn một chút chúng ta chỉ phát biểu mà
không chứng minh .

Định lí 10.2
Giả sử (S,A,K,E) là một mã xác thực ,trong đó

A

=n và
Pd
0
=Pd
1
=1/n.Khi đó Kk(n-1)+1.Hơn nữa K=k(n-1)+1 khi và
chỉ khi có một mảng trực giao 0A(n,k,

),ở đây

S=k,=(k(n-1)+1)/n
2

và p
K
(K)=1/(k(n-1)+1) với mọi khoá KK.

Nhận xét.Chú ý rằng định lí 10.10 tạo ra một lớp vô hạn các mảng trực
giao đạt đợc giới hạn ở định lí 10.12 với dấu =.



R
p
M
(s,a)payoff(s,a)
Nh vậy thoe bất đẳng thức Jensen(dịnh lí (2.5) ta có :
LogPd
0
log
s

S,a

R
p
M
(s,a)payoff(s,a)

s

S,a

R
p
M
(s,a)log payoff(s,a)
Theo phần 10.2:
P
M
(s,a)=p

(a

s) logp
R
(a

s) =-H(AS)
Vietebooks Nguyn Hong Cng
Trang 17
Theo định nghĩa của entropy có điều kiện .Ta sẽ hoàn chỉnh chứng
minh định lí bằng cách chỉ ra rằng: -H(AS)=H(KM)-H(K).Điều
kiện này đợc rút ra từ các đồng nhất thức cơ bản của entropy.Một mặt
ta có :
H(K,A,S)=H(AK,S)+H(AS)+H(S)
Mặt khác ta tính:
H(K,A,S)=H(AK,S)+H(K,S)=H(S)+H(K)
ậ đây ta có sử dụng điều kiện H(AK,S)=0 vì khoá và trạng thái nguồn
sẽ xác định nhãn xác thực một cách duy nhất .Ta cũng dùng đẳng thức
H(AS)=H(K)+H(S) vì nguồn và khoá là các biến cố độc lập.
So sánh hai biểu thức biểu thị H(K,S,A) ta có:
-H(A,S)=H(KA,S)-H(K)
Tuy nhiên thông báo m=(s,a) đợc xác định gồm một trạng thái nguồn
và một trạng thái nhãn xác thực(nghĩa là M=SxA).Bởi vậy:
H(KA,S)=H(KM)
Định lí đợc chứng minh.

Sau đây ta sẽ chỉ đa ra mà không chứng minh giới hạn tơng tự
cho Pd
1
.

trong định lí 10.13 và 10.14 đều đạt đợc với dấu bằng.Trớc hết ta dễ
thấy rằng:
H(K)=logn
2

Vì mỗi một trong n
2
quy tắc xác thực đều đợc chọn đồng xác
suất.Tiếp theo ta sẽ quay lại việc tính toán H(KM).Nừu đã quan sát
đợc một bản tin m=(s,a) nào đó thì điều này sẽ giới hạn các khóa sẽ
nằm trong tập con có lực lợng n.Mỗi khoá trong n khóa này sẽ có
Vietebooks Nguyn Hong Cng
Trang 18
tập con nh nhau .Vì thế H(Km)=logn với bản tin n bất kì .Khi đó ta
có :
H(KM)=
m

M
p
M
(m)H(Km)
=

M
p
M
(m)logn
=log n
Nh vậy ta có:

định lí 10.9 lần đầu tiên đợc chứng minh bởi Placket và Berman vào
1945 trong [PB 45].Nhiều kết quả thú vị về các mảng trực giao có thể
tìm đợc trong nhiều giáo trình khác nhau về lí thuyết thiết kế tổ
hợp(chẳng hạn nh trong [BJL 8] của Beth,Jungickel và Lenz).
Cuối cùng việc sử dụng kĩ thuật entropy trong việc nghiên cứu các
mã xác thực do Simone đa ra .Giới hạn của định lí 10.13 đã đợc
Simone chứng minh trớc tiên trong [Si 85];một cánh chứng minh của
định lí 10.14 có thể tìm đợc trong [Wa 90] của Walker. Vietebooks Nguyn Hong Cng
Trang 19
BI TậP
10.1.Hãy tính Pd
0
và Pd
1
của mã xác thực đợc biểu thị trong ma trận
sau :
Khoá 1 2 3 4
1 1 1 2 3
2 1 2 3 1
3 2 1 3 1
4 2 3 1 2
5 3 2 1 3
6 3 3 2 1
Các phân bố xác suất trên S và K nh sau:
P
s
(1)=p

} và
giả sử B là một 0A(n
2
,k,
2
) trên tập kí hiệu {1, ,n
2
}Ta xây dựng C là
một 0A(n
1
,n
2
,k,
1

2
) trên tập kí hiệu {1 n
1
}x{1 n
2
} nh sau :với mỗi
hàng r
1
=(x
1
x
k
) của A và với mỗi hàng s
1
={y

2
)cho mã xác thực ở bài toán 10.1Phân bố xác suất trên cavcs
dãy của hai nguồn là :

18/1)4.1()3.1()2.1(
222
=
=
=
SSS
ppp9/1)4.2()3.2()1.2(
222
=
=
=
SSS
ppp

9/1)4.3()2.3()1.3(
222
=
=
=
SSS
ppp

18/1)3.4()2.4()1.4(

KM

Ta đã biết cách tính p
M
(m).Để tính p
M
(mk) hãy viết m=(s,a) và
nhận xét thấy rằng :p
M
(mk)=p
S
(s) nếu e
K
(s)=a và p
M
(mk)=0 trong
trờng hợp ngợc lại .