Tr l i câu h i ôn t pả ờ ỏ ậ
Ch ng 1ươ
Câu 1: Lý thuy t đ ph c t p-Ý nghĩa ?ế ộ ứ ạ
Khái ni m đ ph c t p g n v i khái ni m thông tinệ ộ ứ ạ ắ ớ ệ
-Lý thuy t tính toán: Đ ph c t p c a m t v n đ là s b c gi i quy t v n đ bao g m đ ph cế ộ ứ ạ ủ ộ ấ ề ố ướ ả ế ấ ề ồ ộ ứ
t p th i gian và đ ph c t p không gian.ạ ờ ộ ứ ạ
Lý thuy t thông tin: Đ ph c t p Kolmogorov mô t t p các đ c tính c a đ i t ng và là đ dài ng nế ộ ứ ạ ả ậ ặ ủ ố ượ ộ ắ
nh t mô t h u hi u đ i t ng.ấ ả ữ ệ ố ượ
- S b c c n thi t đ gi i quy t bài toán chính là đ ph c t p th i gian và là m t hàm c a đ u vào,ố ướ ầ ế ể ả ế ộ ứ ạ ờ ộ ủ ầ
s l ng tài nguyên không gian s d ng trong thu t toán hay b nh là đ ph c t p không gianố ượ ử ụ ậ ộ ớ ộ ứ ạ
tính toán.
Ý nghĩa c a đ ph c t p:ủ ọ ứ ạ
- Vi c phân tích các mô hình thông qua đ th s giúp ta có đ c các gi i thu t t t nh t cho các bàiệ ồ ị ẽ ượ ả ậ ố ấ
toán liên quan t i đ ph c t p c a h th ng, nh t là các bài toán tìm đ ng, đ nh tuy n trong k thu tớ ộ ứ ạ ủ ệ ố ấ ườ ị ế ỹ ậ
chuy n m ch. Nh v y, k t qu c a lí thuy t đ ph c t p s là quan h đ c bi t c a s phát tri nể ạ ư ậ ế ả ủ ế ộ ứ ạ ẽ ệ ặ ệ ủ ự ể
thu t toán c a các ng d ng th c ti n.ậ ủ ứ ụ ự ễ
- Đ ph c t p tính toán th ng đ c s d ng trong các bài toán thi t k và phân tíchộ ứ ạ ườ ượ ử ụ ế ế
Các thu t toán nh m xác đ nh ph m vi và tính hi u qu c a thu t toánậ ằ ị ạ ệ ả ủ ậ
Ch ng 2:ươ
Câu 2: Nguyên tăc trao đôi khe th i gian nôi TSI? ơ
Trong ky thuât chuyên mach kênh, sau khi tin hiêu thoai đ c ma hoa thanh cac t ma nhi phân 8 bit, ! " ượ " # " ư
cac kênh thông tin đ c xac lâp trên cac khe th i gian cach nhau 125µs va đ c truyên đi nh cac hê" ượ " " ờ " # ượ # ờ "
thông truyên dân va chuyên mach." # # !
Trên nguyên tăc s dung chung tai nguyên, cac thông tin cua ng i s dung đ c chuyên đi trên cac" ử # " ! ườ ử ượ ! "
kênh đ c phân chia logic theo th i gian, s khac biêt cua khe th i gian đ c ân đinh cho nguôn tinượ ờ ự " ! ờ ượ " #
phia phat va nguôn tin phia thu la môt yêu tô yêu câu co s chuyên đôi nôi dung thông tin t khe th i" " # # " # " " # " ự ! ! ư ờ
gian nay sang khe th i gian khac trong cung môt khung, đo chinh la qua trinh trao ñôi khe th i gian nôi# ờ " # " " # " # ! ờ
TSI.
Môt c câu s dung chuyên đôi TSI đ c minh hoa trên hinh d i đây, cac khôi thiêt bi chinh gôm co: ơ " ử ! ! ượ # ướ " " " " # "
1
n
2
0 n 0 n
W r ite
R e a d
R A M
0n0n
0n0n
1 4
4 1
I N
O U T
( t )
1 2 5 m i c r o s e c s
Cac tuyên PCM đâu vao va đâu ra co câu truc khung gôm n khe th i gian, yêu câu chuyên đôi" " # # # # " " " # ờ # ! !
nôi dung thông tin cua môt khe th i gian bât ky t đâu vao t i ñâu ra. ! ờ " # ư # # ớ #
Bô nh l u ñêm tam th i hoat ñông theo nguyên tăc truy xuât ngâu nhiên co dung l ng đu ớ ư ờ " " " ượ !
ch a toan bô thông tin d liêu trong môt khung PCM, (Sô ngăn nh : n, dung l ng ngăn nh : 8 bit).ứ # ữ " ớ ượ ớ
Khôi điêu khiên CM (Control Memory) s dung đê ghi cac thông tin điêu khiên chuyên đôi nôi dung khe" # ! ử ! " # ! ! !
th i gian cho bô nh l u đêm (Sô ngăn nh : n, dung l ng ngăn nh : L= log2n).ờ ớ ư " ớ ượ ớ
Khôi đông bô cho qua trinh ghi đoc vao cac bô nh đ c đông bô thông qua môt bô đêm khe th i gian" # " # # " ớ ượ # " ờ
TS.C.
Khi co yêu câu chuyên đôi nôi dung thông tin va tuy thuôc vao nguôn tai nguyên cua hê thông, khôi" # ! ! # # # # # ! " "
x ly trung tâm se đ a cac d liêu điêu khiên t i khôi điêu khiên CM nhăm săp xêp vi tri chuyên đôi cuaử " ư " ữ # ! ớ " # ! # " " " ! ! !
cac khe th i gian. Đê đam bao tôc đô luông thông tin đâu vao va đâu ra, trong cung môt khoang th i gian" ờ ! ! ! " # # # # # # ! ờ
bô nh l u đêm phai th c hiên đông th i hai tac vu ghi thông tin vao va đoc thông tin ra. Theo nguyên ớ ư ! ự # ờ " # #
tăc trao đôi khe th i gian nôi TSI, đô trê tôi đa cua thông tin trao đôi không v t qua th i gian cua môt" ! ờ " ! ! ượ " ờ !
khung Td (max) = (n-1)TS < 125as.#
Câu 3 :Đ nh lý clos-Ch ng minh đ nh lý?ị ứ ị
-KN: Ma tr n chuy n m ch k t n i 3 t ng không t c ngh n khi và ch khi s k t n i trung gian r2 ≥ nậ ể ạ ế ố ầ ắ ẽ ỉ ố ế ố
+ m -1. Tr ng h p đ c bi t khi n=m thì r2 ≥ 2n-1.ườ ợ ặ ệ
-CM:
Mô hình ghép n i có liên k t đ y đ 3 t ng chuy n m ch đ c th hi n trên hình 2.9ố ế ầ ủ ầ ể ạ ượ ể ệ
(a). Ma tr n chuy n N đ u vào- M đ u ra (nxm) đ c k t n i b i r1 ma tr n t ng A (kích th c n xậ ể ầ ầ ượ ế ố ở ậ ầ ướ
r2 ), r2 ma tr n t ng B (kích th c r1 x r3) và r3 ma tr n t ng C (kích th c r2 x m). V i gi thi tậ ầ ướ ậ ầ ướ ớ ả ế
r2=1, r1=n và r3=m ta có mô hình k t n i:ế ố
M t ma tr n chuy n m ch không t c ngh n hoàn toàn khi toàn b các yêu c u đ u vào b t kỳ đ cộ ậ ể ạ ắ ẽ ộ ầ ầ ấ ượ
đ u n i t i các đ u ra b t kỳ. Gi thi t có (n-1) đ ng vào yêu c u chi m, v y có (n-1) đ ng liênấ ố ớ ầ ấ ả ế ườ ầ ế ậ ườ
k t gi a t ng A và t ng B b chi m. T ng t nh v y, n u đ u ra có (m-1) đ ng b chi m thì sế ữ ầ ầ ị ế ươ ự ư ậ ế ầ ườ ị ế ẽ
có (m-1) đ ng liên k t gi a t ng B và t ngc b chi m.ườ ế ữ ầ ầ ị ế
Tr ng h p x u nh t x y ra khi (n-1) đ ng liên k t A-B đ u n i t i các kh i chuy nườ ợ ấ ấ ả ườ ế ấ ố ớ ố ể
m ch t ng B khác bi t hoàn toàn v i (m-1) đ ng liên k t B-C. V y t ng s kh i chuy n m chạ ầ ệ ớ ườ ế ậ ổ ố ố ể ạ
trong t ng B b ng [(n-1) + (m-1)] đ đ m b o không t c ngh n ngay c khi tr ng h p x u nh tầ ằ ể ả ả ắ ẽ ả ườ ợ ấ ấ
x y ra.ả
Ma tr n chuy n m ch không t c ngh n hoàn toàn khi đ ng vào th n c a t ng Aậ ể ạ ắ ẽ ườ ứ ủ ầ
K t n i đ c đ ng ra th m c a t ng C, d n đ n s l ng kh i chuy n m ch trong Bế ố ượ ườ ứ ủ ầ ẫ ế ố ượ ố ể ạ
T i thi u ph i d 1 kh i cho đ ng d n cu i cùng này. Hay nói cách khác s l ng liên k t t i thi uố ể ả ư ố ườ ẫ ố ố ượ ế ố ể
r2 ≥ (n-1) + (m-1) +1 = n + m -1.
N u ma tr n chuy n m ch là ma tr n vuông (N=M), (n = m) và (r1 = r2), ta có s l ng đi m k tế ậ ể ạ ậ ố ượ ể ế
n i chéo là:ố
C = 2nr2 + r12r2 = 2n(2n-1) + r12 (2n-1) = (2n-1) ( 2N + N2 ∕ n2 )
Khi kích th c c a tr ng chuy n m ch l n, n l n ta có th tính s l ng đi m k tướ ủ ườ ể ạ ớ ớ ể ố ượ ể ế
N i chéo C x p x theo công th c 2.4 sau.ố ấ ỉ ứ
C ~= 2n (2N + N2∕n2 )= 4nn + 2N2∕n
Đ t i u s đi m k t n i chéo, l y vi phân C theo n: (dc/dn) và cho k t qu ti n t i 0ể ố ư ố ể ế ố ấ ế ả ế ớ
Ta có
N ≈ (N/2)1/2
Suy ra C 1 4 2.N 3/ 2 n
Nh trên công th c 2.6 ch rõ, chuy n m ch k t n i 3 t ng Clos gi m đ ph c t pư ứ ỉ ể ạ ế ố ầ ả ộ ứ ạ
Ph n c ng xu ng còn N3/2 thay vì N2 trong ma tr n k t n i crossbar mà v n đ m b o đ c m cầ ứ ố ậ ế ố ẫ ả ả ượ ụ
tiêu không t c ngh n.ắ ẽ
Câu 4: Trình bày ph ng pháp tìm ki m ki u m t n ch n kênh?ươ ế ể ặ ạ ọ
KN: Ph ng pháp đ c đ xu t đ tìm ki m các c p bit r i t i hai đ u đ u vào T1 và đàu ra T2 làươ ượ ề ấ ể ế ặ ỗ ạ ầ ầ
ph ng pháp tìm ki m ki u m t n ch n kênhươ ế ể ặ ạ ọ
NT:
-Các bit trong thanh ghi ch th tr ng thái và thanh ghi m t n th hi n rõ s b n/r i c a các kênhỉ ị ạ ặ ạ ể ệ ự ậ ỗ ủ
thông qua b n đ nh ánh x tr ng thái.ả ồ ớ ạ ạ
Hình 2.11 d i đây ch ra nguyên t c ho t đ ng c a ph ng pháp m t n ch n kênhướ ỉ ắ ạ ộ ủ ươ ặ ạ ọ
- Thanh ghi tr ng thái là s đ ánh x tr ng thái hi n th i c a các kênh đ c ch n (bitạ ơ ồ ạ ạ ệ ờ ủ ượ ọ
1 th hi n tr ng thái r i c a kênh, bit 0 th hi n tr ng thái b n c a kênh)ể ệ ạ ỗ ủ ể ệ ạ ậ ủ
-Thanh ghi m t n là m t logic nh phân có đ dài b ng thanh ghi tr ng thái, trên đó t n t i 02 bit cóặ ạ ộ ị ộ ằ ạ ồ ạ
giá tr 1 và còn l i là các bit có giá tr 0. Thanh ghi m t n có nhi m v l a ch n 2 khe th i gian r iị ạ ị ặ ạ ệ ụ ự ọ ờ ỗ
(đ u vào và đ u ra) cho k t n i.ầ ầ ế ố
3 thu t toán th ng đ c s d ng trong cách th c di chuy n m t n g m: Ng u nhiên – liên ti p, cậ ườ ượ ử ụ ứ ể ặ ạ ồ ẫ ế ố
đ nh- liên ti p và ph ng pháp th l pị ế ươ ử ặ
Ph ng pháp ng u nhiên - liên ti p: ph ng pháp này d a trên nguyên t c tìm ki m ng uươ ẫ ế ươ ự ắ ế ẫ
nhiên m t khe th i gian r i, n u khe th i gian đ u tiên ch n ng u nhiên không tho mãn yêu c u, hộ ờ ỗ ế ờ ầ ọ ẫ ả ầ ệ
th ng d ch chuy n liên ti p trong toàn d i nh m tìm khe th i gian tho mãn yêu c u. Ph ng phápố ị ể ế ả ằ ờ ả ầ ươ
này t o ra hi u ng chi m d ng c c b t các đi m xác l p ng u nhiên, th i gian tìm ki m s kéo dàiạ ệ ứ ế ụ ụ ộ ư ể ậ ẫ ờ ế ẽ
khi s l ng kênh b chi m tăng lên.ố ượ ị ế
(ii) Ph ng pháp c đ nh – liên ti p: Ph ng pháp này ch đ nh khe th i gian đ u tiênươ ố ị ế ươ ỉ ị ờ ầ
sau đó tìm liên ti p trên toàn d i. Hi u ng tr i dài các kênh b chi m d ng b t đ u t kênh đ cế ả ệ ứ ả ị ế ụ ắ ầ ư ượ
ch n và xác su t ch n kênh trong ph ng pháp này không gi ng nhau.ọ ấ ọ ươ ố
(iii) Ph ng pháp th l p: Ph ng pháp này d a trên đ c tính c a l u l ng yêu c uươ ử ặ ươ ự ặ ủ ư ượ ầ
và s chi m d ng ng u nhiên c a các khe th i gian. Quá trình th l p d a trên theo kho ng th i gianự ế ụ ẫ ủ ờ ử ặ ự ả ờ
chi m d ng khe th i gian. Ph ng pháp này đ c bi t hi u qu n uế ụ ờ ươ ặ ệ ệ ả ế
mô hình l u l ng đ u vào đ c xác đ nh.ư ượ ầ ượ ị
Ch ng 3:ươ
Câu6: Câu truc ch c năng, nguyên ly hoat đông cua tr ng chuyên mach không gian sô, th i gian ứ ươ ơ
sô, tr ng chuyên mach ghep ư ?
I-Tr ng chuyên mach không gian sô:ườ ! "
D E C
0
1
2
n
Béc h än
Bé ® Õ m T S
§ån g h å
TÝn h i Öu g h i
SèliÖu
C - M E M
A d d
R /W
B
é
®i
Ò
uk h i
Ó
n
k h u v
ù
c
Bé ®iÒu k h iÓn k h u v ùc
B
é
®i
Ò
uk h i
Ó
n
k h u v
ù
c
C ¸ c ®ên g v µo
C ¸ c ®ên g r a
C h u y Ón m ¹c h k h « n g g ia n tÝn h iÖu s è
1
N
1M
K h u n g P C M ® Ç u v µo
K h u n g P C M ® Ç u r a
Nguyên ly chuyên mach không gian S" !
Câu truc ch c năng:" " ứ
Tâng chuyên mach không gian sô đ c câu tao t môt ma trân chuyên mach mxn va môt bô điêu khiên# ! " ượ " ư ! # # !
khu v c:ự
Ma trân chuyên mach gôm: m đâu vao va n đâu ra trong đo, lôi vao t ng ng v i cac hang va lôi ra ! # # # # # " " # ươ ứ ớ " # # "
t ng ng v i cac côt. Tai giao điêm cua hang va côt la cac tiêp điêm chuyên mach (AND hoăc logic 3ươ ứ ớ " ! ! # # # " " ! !
trang thai). Cac tiêp điêm nay đ c điêu khiên b i bô điêu khiên khu v c (LOC) qua hê thông đ ng " " " ! # ượ # ! ở # ! ự " ườ
BUS.
Bô điêu khiên khu v c gôm: # ! ự #
Bô đêm khe th i gian (TS – COUNT) đêm cac khe th i gian đông bô đ a vao bô chon tin hiêu. " ờ " " ờ # ư # "
Bô chon tin hiêu (SEL) chon tin hiêu ghi đoc cho C-MEM. " "
Bô nh C-MEM l u đia chi liên quan t i cac tiêp điêm chuyên mach t ng ng v i TS cân chuyên ớ ư ! ớ " " ! ! ươ ứ ớ # !
mach, co sô ngăn nh băng sô khe th i gian trong tuyên PCM. " " ớ # " ờ "
Bô giai ma đia chi (DEC). Chuyên đôi cac tin hiêu đia chi điêu khiên t C-MEM t i cac tiêp điêm ! ! ! ! " " ! # ! ư ớ " " !
chuyên mach.!
Nguyên tăc hoat đông:"
Nguyên tăc c ban cua môt c chê chuyên mach nay la chuyên nôi dung thông tin cua môt TS* đâu vao" ơ ! ! ơ " ! # # ! ! # #
t i TS* đâu ra co cung chi sô th i gian nh ng khac tuyên. Theo nguyên tăc nay thi tiêp điêm chuyênớ # " # ! " ờ ư " " " # # " ! !
mach cân phai m trong suôt qua trinh chuyên thông tin trong khe th i gian đo, va qua trinh m thông # ! ở " " # ! ờ " # " # ở
nay se đ c lăp lai theo chu ki 125 micro giây. Tât nhiên la khoang th i gian con lai trong khung (cac TS# ượ # " # ! ờ # "
khac) se đ c s dung cho cac cuôc nôi khac (theo cac biêu đô th i gian đ c điêu khiên t i C-MEM)." ượ ử " " " " ! # ờ ượ # ! ớ
C chê nay thay đôi vê măt không gian cua tin hiêu va co thê xay ra tôn thât nôi khi co nhiêu h n môtơ " # ! # ! " # " ! ! ! " " # ơ
đâu vao đâu nôi t ng ng t i môt tuyên đâu ra.# # " " ươ ứ ớ " #
Cac ma trân s dung th ng la ma trân vuông kich th c (nxn)" ử ườ # " ướ
Nhân xet: "
Tr ng chuyên mach không gian S mang tinh th i gian nêu xet vê tinh chu ky cua qua trinh đong ngătườ ! " ờ " " # " # ! " # " "
tiêp ñiêm, tuy nhiên chu ky nay la cô ñinh cho tât ca cac cuôc nôi qua tr ng chuyên mach. Nh c điêm" ! # # # " " ! " " ườ ! ượ !
luôn tôn tai trong cac tr ng chuyên mach không gian S la kha năng tăc nghen khi co nhiêu h n môt# " ườ ! # ! " " # ơ
yêu câu chuyên mach TS đâu vao cung muôn ra môt công đâu ra.# ! # # # " ! #
Môt ma trân chuyên mach không tăc nghen hoan toan đ c ñinh nghia la môt ma trân co kha năng đap ! " # # ượ # " ! "
ng đ c cac kêt nôi t cac đâu vao bât ky t i cac đâu ra bât ky. Hiên t ng tranh châp công đâu raứ ượ " " " ư " # # " # ớ " # " # ượ " ! #
trong nôi bô tr ng chuyên mach đ c goi la hiên t ng tăc nghen nôi. Đê giai quyêt vân đê trên, cac ườ ! ượ # ượ " ! ! " " # "
tr ng chuyên mach S th ng đ c kêt h p v i cac bô đêm gây trê th i gian đê tranh tranh châp, giaiườ ! ườ ượ " ợ ớ " ờ ! " " !
phap ghep nôi v i tr ng chuyên mach th i gian T đ c s dung phô biên trong cac hê thông chuyên" " " ớ ườ ! ờ ượ ử ! " " " !
mach hiên nay.
II-Tr ng chuyên mach th i gian sô:ườ ! ờ "
Tr ng chuyên mach th i gian T co hai kiêu điêu khiên: điêu khiên đâu vao th c hiên qua trinh ghiườ ! ờ " ! # ! # ! # # ự " #
thông tin co điêu khiên va đoc ra tuân t ; điêu khiên đâu ra th c hiên ghi thông tin tuân t va đoc" # ! # # ự # ! # ự # ự #
ra theo điêu khiên. Trong muc nay ta xem xet nguyên ly hoat đông cua tr ng chuyên mach T theo# ! # " " ! ườ !
kiêu điêu khiên đâu ra.! # ! #
Câu truc ch c năng:" " ứ
Tr ng chuyên mach th i gian T đ c câu tao t 2 khôi chinh: Khôi bô nh thoai SMEMườ ! ờ ượ " ư " " " ớ
(Speech memory) va khôi điêu khiên cuc bô LOC.# " # !
Khôi bô nh thoai SMEM la môt thiêt bi ghi nh truy xuât ngâu nhiên RAM (Sô l ng ngăn nh : n;" ớ # " ớ " " ượ ớ
dung l ng ngăn nh : 8 bit). Nh vây, bô nh SMEM l u toan bô thông tin trong môt khung tin hiêuượ ớ ư ớ ư # "
PCM đê đam bao tôc đô luông thông tin qua tr ng chuyên mach, tôc đô ghi đoc cua CMEM phai! ! ! " # ườ ! " ! !
l n gâp 2 lân tôc đô luông trên tuyên PCM đâu vao hoăc đâu ra.ớ " # " # " # # #
Khôi điêu khiên khu v c gôm môt sô khôi nh : Bô nh điêu khiên CMEM l u tr cac thông tin điêu" # ! ự # " " ư ớ # ! ư ữ " #
khiên SMEM, sô th t cua ngăn nh va nôi dung d liêu trong CMEM thê hiên cac chi sô khe th i! " ứ ự ! ớ # ữ ! " ! " ờ
gian TS cân trao đôi nôi dung tin. TS.C nhân tin hiêu t đông hô hê thông đê điêu khiên cac bô chon# ! " ư # # " ! # ! "
SEL1, SEL2 nhăm đông bô hoa qua trinh ghi đoc thông tin d liêu cho CMEM va SMEM.# # " " # ữ #