Bài giảng Truyền số liệu mạng - Chương 3: Kỹ thuật thông tin dữ liệu

còn có thể sửa sai ở một số vị trí nhất định
„ Ví dụ :
„ Để mã hóa các số thập phân từ 0 – F ta cần 4 bit. Gọi 4 bit đó là m3m2m1m0.
„ Trước khi truyền ta chèn vào 3 bit kiểm tra c2c1c0., 3 bit này được tính bằng cách EX-
OR :
„ c0 = m0 + m1 + m3
„ c1 = m0 + m2 + m3
„ c2 = m1 + m2 + m3
„ Đầu thu thực hiện kiểm tra bằng cách tính :
„ p0 = c0 + m0 + m1 + m3
„ p1 = c1 + m0 + m2 + m3
„ p2 = c2 + m1 + m2 + m3
+ Nếu không sai thì p0 = p1 = p2 = 0
+ Nếu sai thì thì số nhị phân p2p1p0 là vị trí của bit sai (các bit trong từ mã
Hamming truyền đi được đánh thứ tự từ 0 đến 7) và sửa bằng cách đảo bit này.
ĐQH-V2008 TSL&MTTS C3-91
Hamming
Calculating the Hamming Code 
„ The key to the Hamming Code is the use of extra parity bits to allow the identification of a 
single error. Create the code word as follows: 
1. Mark all bit positions that are powers of two as parity bits. (positions 1, 2, 4, 8, 16, 32, 64, etc.) 
2. All other bit positions are for the data to be encoded. (positions 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 
15, 17, etc.) 
3. Each parity bit calculates the parity for some of the bits in the code word. The position of the 
parity bit determines the sequence of bits that it alternately checks and skips. 
- Position 1: check 1 bit, skip 1 bit, check 1 bit, skip 1 bit, etc. (1,3,5,7,9,11,13,15,...)
- Position 2: check 2 bits, skip 2 bits, check 2 bits, skip 2 bits, etc. (2,3,6,7,10,11,14,15,...)
- Position 4: check 4 bits, skip 4 bits, check 4 bits, skip 4 bits, etc. 
(4,5,6,7,12,13,14,15,20,21,22,23,...)
- Position 8: check 8 bits, skip 8 bits, check 8 bits, skip 8 bits, etc. (8-15,24-31,40-47,...)
- Position 16: check 16 bits, skip 16 bits, check 16 bits, skip 16 bits, etc. (16-31,48-63,80-95,...)
- Position 32: check 32 bits, skip 32 bits, check 32 bits, skip 32 bits, etc. (32-63,96-127,160-
191,...)
etc. 
4. Set a parity bit to 1 if the total number of ones in the positions it checks is odd. Set a parity bit 
to 0 if the total number of ones in the positions it checks is even.
5. -> Then the receiver could calculate which bit was wrong and correct it. The method is to verify 
each check bit. Write down all the incorrect parity bits. Doing so, you will discover that parity 
bits 2 and 8 are incorrect. It is not an accident that 2 + 8 = 10, and that bit position 10 is the 
location of the bad bit. In general, check each parity bit, and add the positions that are wrong, 
this will give you the location of the bad bit. 
ĐQH-V2008 TSL&MTTS C3-92
Here is an example: 
„ A byte of data: 10011010
Create the data word, leaving spaces for the parity bits: _ _ 1 _ 0 0 1 _ 1 0 1 0
Calculate the parity for each parity bit (a ? represents the bit position being set): 
„ - Position 1 checks bits 1,3,5,7,9,11: 
? _ 1 _ 0 0 1 _ 1 0 1 0. Even parity so set position 1 to a 0: 0 _ 1 _ 0 0 1 _ 1 0 1 0 
„ - Position 2 checks bits 2,3,6,7,10,11:
0 ? 1 _ 0 0 1 _ 1 0 1 0. Odd parity so set position 2 to a 1: 0 1 1 _ 0 0 1 _ 1 0 1 0 
„ - Position 4 checks bits 4,5,6,7,12:
0 1 1 ? 0 0 1 _ 1 0 1 0. Odd parity so set position 4 to a 1: 0 1 1 1 0 0 1 _ 1 0 1 0
„ - Position 8 checks bits 8,9,10,11,12:
0 1 1 1 0 0 1 ? 1 0 1 0. Even parity so set position 8 to a 0: 0 1 1 1 0 0 1 0 1 0 1 0
„ -> Code word: 011100101010. 
„ The above example created a code word of 011100101010. Suppose the word that was received was 
011100101110 instead. Then the receiver could calculate which bit was wrong and correct it. The method is to 
verify each check bit. Write down all the incorrect parity bits. Doing so, you will discover that parity bits 2 and 8 
are incorrect. It is not an accident that 2 + 8 = 10, and that bit position 10 is the location of the bad bit. In 
general, check each parity bit, and add the positions that are wrong, this will give you the location of the bad 
bit. 
„ Try one yourself 
„ Test if these code words are correct, assuming they were created using an even parity Hamming Code . If one 
is incorrect, indicate what the correct code word should have been. Also, indicate what the original data was. 
010101100011 
111110001100 
000010001010 
ĐQH-V2008 TSL&MTTS C3-93
3.8 Kỹ thuật nén dữ liệu
„ Mục đích : Giảm kích thước và thời gian truyền.
„ Các kỹ thuật nén cơ bản :
„ Packed Decimal : Khi truyền ký tự số dùng mã BCD 4 bit 
thay cho mã ASCII 7bits hay EDBIC
„ Relative Coding : Khi truyền các ký tự số, chỉ truyền sai số
giữa các số liên tiếp nhau.
„ Character Suppression : Khi truyền các ký tự in được mà
các ký tự giống nhau được truyền liên tiếp, thay vì truyền hết
các ký tự thì chỉ truyền 1 ký tự đại diên và kèm theo là số các
ký tự giống nhau.
„ Huffman Coding
„ Run Length Coding (Facsimile compression)
ĐQH-V2008 TSL&MTTS C3-94
Kỹ thuật nén dữ liệu
„ Huffman Coding
„ Là một mã thống kê tối ưu
„ Các tin xuất hiện nhiều, xác suất xuất hiện lớn thì
được mã hóa bằng từ mã ngắn và ngược lại. Do đó
độ dài trung bình của các từ mã sẽ nhỏ nhất, làm
giảm thiểu rất nhiều lượng thông tin truyền trên
đường dây nên giảm sai số.
ĐQH-V2008 TSL&MTTS C3-95
Kỹ thuật nén dữ liệu
„ Huffman Coding
„ Ví dụ : Để tạo mã cho việc đo nhiệt độ từ 200 đến 300 C người ta lấy xác suất của nó và
được sắp xếp thứ tự xuất hiện như bảng.
„ Sắp xếp các khả năng xuất hiện theo thứ
tự giảm dần.
„ Hai giá trị 0,1 gán cho 2 khả năng xuất
hiện nhỏ nhất, 2 khả năng này gộp lại
thành 1 và sắp xếp theo thứ tự giảm dần. 
Tương tự như vậy cho đến 2 khả năng
cuối cùng (tổng sẽ = 1).
„ Mã tương ứng của mỗi nhiệt độ được
hình thành bằng cách chọn các bit 0,1 
trên đường đi xuất phát từ mức nhiệt độ
đến ngọn.
„ Bit LSM sẽ nằm bên trái cây.
30
20
29
21
28
22
27
23
26
24
25
0,02
0,03
0,04
0,05
0,05
0,06
0,10
0,12
0,15
0,17
0,21
0
1
0
1
0
1
0,05
1
0
0,10
0,32
0
1
0,09
0
1 0,15
0,20
0
1
0
0,27
0,41
0
1
0,59
0
1 1
Từ mã0C P
10
000
001
011
010001
010000
01001
1111
1110
0101
110
ĐQH-V2008 TSL&MTTS C3-96
Kỹ thuật nén dữ liệu
„ Huffman Coding
„ Hiệu suất sử dụng từ mã (entropy)
H(x)=∑pi log2 (1/pi) (bits/symbol) = 3,14
„ Chiều dài trung bình của từ mã.
N = ∑ piNi (bits/symbol) = 3,18 ;4
„ Hiệu suất của mã hóa
h = H(x)/N = 98% ;78%
„ Tốc độ bit nhị phân
R= rN
ĐQH-V2008 TSL&MTTS C3-97
Kỹ thuật nén dữ liệu
„ Run Length Coding (Facsimile compression)
„ Sử dụng trong máy Facsimile trắng đen.
„ Một trang Fax được chia
„ Theo chiều dọc khoảng khoảng 3.85 hoặc 7.7 lines/mm, 
tương đương 100 hoặc 200 lines / inche
„ Mỗi line được số hoá với tốc độ 8.05 phần tử ảnh (pels)/mm.
„ Mỗi điểm ảnh trắng mã hoá ‘0’, điểm đen mã hoá ‘1’
„ Một trang Fax khi chưa nén được mã hóa khoảng 2 
triệu bits.
ĐQH-V2008 TSL&MTTS C3-98
Kỹ thuật nén dữ liệu
ĐQH-V2008 TSL&MTTS C3-99
Kỹ thuật nén dữ liệu
„ Run Length Coding (Facsimile compression)
„ Thực tế khi truyền bức Fax thì sẽ có những line mà có khoảng
điểm ảnh trắng hay đen liên tục, để giảm bớt số bit trước khi
truyền ta dùng phương pháp nén Facsimile:
„ Các từ mã cố định và chia thành 2 nhóm the termination-codes (Hình a: 
Chiều dài từ 0 – 63 pixel) và the make-up codes (Hình b: Chiều dài là
k x 64 pixel).
„ Để bên nhận đồng bộ thì ký mã EOL(End Of Line) được thêm vào ở
cuối mỗi line.
„ Kết thúc trang là chuỗi 6 EOL liện tiếp.
„ Trong trường hợp bên thu không giải mã được EOL thì sẽ ngưng quá
trình nhận và thông báo cho bên phát biết.
ĐQH-V2008 TSL&MTTS C3-100
Kỹ thuật nén dữ liệu
ĐQH-V2008 TSL&MTTS C3-101
Transmission Control Circuits
„ Universal asynchronous receiver 
transmitter (UART)
„ Start and stop bit insertion and deletion
„ Bit (clock synchronization)
„ Character synchronization
„ Parity bit generation and checking per 
character (BCC computed by controlling 
device)
ĐQH-V2008 TSL&MTTS C3-102
Transmission Control Circuits
„ Universal synchronous receiver 
transmitter
„ Low bit rate DPLL clock synchronization
„ Character synchronization
„ Synchronous idle character generation
„ Parity generation and checking per character 
(BCC computed by controlling device)
ĐQH-V2008 TSL&MTTS C3-103
Transmission Control Circuits
„ Universal synchronous / asynchronous 
receiver transmitter (USART)
„ Can be programmed to operate as either a 
UART or USRT
„ Has all programmable features of both 
devices
ĐQH-V2008 TSL&MTTS C3-104
Transmission Control Circuits
„ Bit-oriented protocol circuits (BOPs)
„ Opening and closing flag insertion and 
deletion
„ Zero bit insertion and deletion
„ CRC generation and checking
„ Idle pattern generation
ĐQH-V2008 TSL&MTTS C3-105
Transmission Control Circuits
„ Universal communication control circuits
„ Can be programmed to operate either UART, 
a USRT or a BOP
„ Has all the programmable features of each 
circuit
ĐQH-V2008 TSL&MTTS C3-106
ĐQH-V2008 TSL&MTTS C3-107
Communications Control Devices
„ Simple terminal networks
„ Multiplexer-based networks
ĐQH-V2008 TSL&MTTS C3-108
Communications Control Devices
ĐQH-V2008 TSL&MTTS C3-109
Communications Control Devices
ĐQH-V2008 TSL&MTTS C3-110
ĐQH-V2008 TSL&MTTS C3-111
Time-division Multiplexer
ĐQH-V2008 TSL&MTTS C3-112
Time-division Multiplexer
ĐQH-V2008 TSL&MTTS C3-113
Statistical Multiplexer
ĐQH-V2008 TSL&MTTS C3-114
ĐQH-V2008 TSL&MTTS C3-115
Block-mode Devices
„ Multidrop (multipoint) lines
„ Cluster controller
„ Hub-polling
ĐQH-V2008 TSL&MTTS C3-116
Block-mode Devices
ĐQH-V2008 TSL&MTTS C3-117
Block-mode Devices
ĐQH-V2008 TSL&MTTS C3-118
Block-mode Devices
ĐQH-V2008 TSL&MTTS C3-119
Summary