CHƯƠng 1 TỔng quan về KỸ thuật truyền số liệU



tải về 0.93 Mb.
trang6/9
Chuyển đổi dữ liệu07.07.2016
Kích0.93 Mb.
1   2   3   4   5   6   7   8   9

3.3.2 Mã Run length :

Mã Huffman tuy có làm giảm số bít truyền đi nhưng nó đòi hỏi dữ liệu phải được tập hợp thành từng nhóm hay ký tự để xác định tần số lặp lại của các nhóm hay ký tự này. Việc này đôi khi rất khó thực hiện đối với một số loại dữ liệu thí dụ như dữ liệu từ một bản fax, tín hiệu mã hình ảnh . . .

Lấy thí dụ trường hợp bản fax, dữ liệu được phát đi không phải là các ký tự mà là các bít tương ứng với điểm sáng tối trên tờ giấy, như vậy phải có một kỹ thuật phù hợp để nén chuỗi dữ liệu này, đó chính là mã Run length.

Mã Run length được tạo ra bằng cách quan sát chuỗi bit 0 (hoặc 1) liên tiếp và thay thế chiều dài chuỗi bít này bởi một số nhị phân. Ở máy thu khi nhận được các số nhị phân sẽ thay các số này bởi các bít 0 (hoặc 1) đồng thời chèn các bít khác loại vào.

Thí dụ ta phải tạo mã Run length cho chuỗi dữ liệu sau bằng cách dùng số 4 bít thay cho số bit 0 liên tiếp:

Dòng dữ liệu 0 . . . 0 1 0 . . . 0 1 1 0 . . . 0 1 0 . . . 0 1 1 0 . . . 0 91 bít

Số bít 0 liên tiếp 14 9 20 30 11

Run length (nhị phân) 1110 1001 0000 1111 0101 1111 1111 0000 0000 1011 40 bít

Run length (thập phân) 14 9 0 15 5 15 15 0 0 11

Nhận xét cách tạo mã :

- 1 bít 1 giữa các chuỗi bít 0 sẽ không được mã, máy thu tự động chèn bít 1 này vào khi phục hồi dữ liệu.

- Nếu có 2 bít 1 liên tiếp, ta xem như có 1 chuỗi gồm không bít 0 giữa 2 bít 1 này và phải được thay thế bởi số 0000.

- Nếu số số 0 nhiều hơn 15 ta phải dùng 2 số nhị phân thay cho chuỗi này (20=15+5; 30=15+15). Ở máy thu khi gặp chuỗi bốn bít 1 nó phải hiểu là phải lấy tổng số này với các số phía sau, nếu số sau cùng cũng gồm 4 bít 1, máy thu phải được báo bằng chuỗi 4 bít 0 theo sau (trường hợp sau số 30)

- Nếu chuỗi dữ liệu bắt đầu bằng bit 1 thì máy phát sẽ gửi đi 4 bít 0 đầu tiên.

Kỹ thuật nén này chỉ có hiệu quả khi chuỗi dữ liệu chứa rất nhiều một loại bit.

Ngoài ra, kỹ thuật nén Run length cũng được dùng mã hóa các chuỗi ký tự giống nhau bằng cách thay mỗi chuỗi ký tự liên tiếp bằng con số chỉ độ dài đứng trước ký tự đó.

Thí dụ, với chuỗi

HHHHHFFFFFFFFYYYYYYYYYYYYYGGGGGGGGGG

Sẽ có mã là: 5H8F13Y10G
3.3.3 Mã vi phân (Differential encoding) :

Còn gọi là mã tương đối (Relative encoding)

Trong nhiều trường hợp, các dữ liệu liên tiếp nhau thay đổi rất ít . Thí dụ trường hợp mã tín hiệu hình ảnh trong kỹ thuật video, do phải xử lý 30 bán ảnh (khung) trong một giây để tạo ảnh động, nên chi tiết của các ảnh không khác nhau bao nhiêu, thay vì phải nén tín hiệu từng khung người ta nghĩ tới việc xác định sự khác nhau của các khung liên tiếp, mã thông tin này và gửi đi.

Nguyên tắc của mã vi phân như sau: khung thứ nhất được phát đi đồng thời lưu ở bộ đệm của máy phát và thu. Máy phát sẽ so sánh khung thứ hai với khung thứ nhất này, mã sự khác biệt và phát đi dưới dạng một khung. Máy thu khi nhận khung thứ hai, nhờ các mã chỉ sự khác biệt mà so sánh với khung thứ nhất (đã lưu trước đó) để tái tạo khung thứ hai, đồng thời nó lưu khung thứ hai này trong bộ đệm và quá trình tiếp tục với các khung mới.

(H 3.5) là một thí dụ minh họa.


5 7 6 2 8 6 6 3 5 6

6 5 7 5 5 6 3 2 4 7

8 4 6 8 5 6 4 8 8 5

5 1 2 9 8 6 5 5 6 6

5 5 2 9 9 6 8 9 5 1

Khung thứ nhất



5 7 6 2 8 6 6 3 5 6

6 5 7 6 5 6 3 2 3 7

8 4 6 8 5 6 4 8 8 5

5 1 3 9 8 6 5 5 7 6

5 5 2 9 9 6 8 9 5 1

Khung thứ nhì



5 7 6 2 8 6 6 3 5 6

6 5 8 5 5 6 3 3 3 7

8 4 6 8 5 6 4 8 8 5

5 1 3 9 7 6 5 5 8 6

5 5 2 9 9 6 8 9 5 1

Khung thứ ba






0 0 0 0 0 0 0 0 0 0

0 0 0 1 0 0 0 0 -1 0

0 0 0 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0 1 0

0 0 0 0 0 0 0 0 0 0

Khung phát đi là sai biệt giữa khung thứ nhì và khung thứ nhất



0 0 0 0 0 0 0 0 0 0

0 0 1 0 0 0 0 1 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 -1 0 0 0 1 0

0 0 0 0 0 0 0 0 0 0

Khung phát đi là sai biệt giữa khung thứ ba và khung thứ nhì



(H 3.5)


Dữ liệu gồm các số nguyên được biểu diễn trong một khung 2 chiều, chúng không mang một ý nghĩa cụ thể nào, mục đích của thí dụ là để hiểu cách tạo mã. Khung thứ nhất chứa một tập hợp các số nguyên và khung thứ hai chứa một tập hợp các số nguyên khác khung thứ nhất một ít.

Trong hình, các khung nằm dưới khung thứ hai và thứ ba là khung chứa các mã vi phân, số 0 chỉ không có sự khác biệt dữ liệu của 2 khung, số1chỉ dữ liệu khung sau lớn hơn khung trước 1 đơn vị và số -1 chỉ ngược lại. Dĩ nhiên có thể sử dụng các số khác hơn là 1 và -1.

Thí dụ cho ta thấy sự xuất hiện một chuỗi dài các bít 0 và có thể được nén nhờ phương pháp Run length.

 


3.4  MẬT MÃ :                                                                                       

                                                                                            

          Trong nhiều trường hợp, bản tin cần được giữ bí mật đối với đệ tam nhân thì việc mã hóa được thực hiện dưới dạng mật: bản tin được mã bởi một khóa mà chỉ hai người liên hệ trong trao đổi thông tin biết để sử dụng khi mã hóa và giải mã.

Gọi bản tin ban đầu là P (Plaintext), bản tin đã cài mật mã là C (Ciphertext) thì C = Ek(P), E và k là giải thuật và khóa tạo mã ( Algorithm & Encryption key). Nơi nhận, nhận bản tin C và phục hồi lại P với giải thuật và khóa là D và k’ : P =Dk(C) = Dk Ek(P). Trong đa số trường hợp (nhưng không phải luôn luôn) k=k’.

Giải thuật và khóa càng phức tạp thì độ an toàn của bản tin càng cao.

Chúng ta sẽ xét một số cách tạo mật mã từ đơn giản đến phức tạp.

 

            3.4.1. Mã Caesar.                                                                                                                           



           3.4.2. Mã đa mẫu tự.

            3.4.3. Mã chuyển vị.

            3.4.4. Mã DES.

 

3.4.1. Mã Caesar (Caesar cipher) :



Còn gọi là mã mẫu tự đơn (mono-alphabetic cipher)

Ðây là loại mật mã có sớm nhất và đơn giản nhất. Người ta sẽ thay các ký tự của bản tin bằng các ký tự khác theo một qui luật nào đó, thí dụ bằng cách cộng một số nguyên vào mã ASCII của các ký tự ta sẽ có một bản tin mật. Thí dụ cộng 1 vào mã ASCII ta sẽ có ký tự B thay cho A, C thay cho B . . . . Và nơi nhận sẽ giải mã bằng cách trừ 1 cho các mã nhận được trước khi tra bảng mã ASCII.

Vì giải thuật tạo mã quá đơn giản nên bản tin có thể được giải mã một cách dễ dàng mà không cần biết trước khóa. Thí dụ, trong tiếng Anh, các ký tự E, T, O và N là các ký tự thường xuất hiện nhiều lần trong các văn bản nên khi gặp bản mã người ta có thể thay các ký tự lặp lại nhiều lần bằng các ký tự này. Sau vài thử nghiệm có thể thấy được qui luật và suy ra bản tin.

Ðể minh họa, giả sử một người nhận được bản tin sau:


{;RSDR\SFF\,PMRU \YP\,U \NSML \ SVVPIMY \ $234567890

Trước nhất người ta liệt kê các ký tự thường xảy ra : \ (7 lần), S (4 lần), R, P và M (3 lần), như vậy người ta có thể thay thử các ký tự S, R, P, M bởi E, T, O, A và N (in đậm):


{;EADE \AFF \,ONEU \YO \,U \NANL \AVVOINY \$234567890

Tiếp tục, người ta có thể nghĩ là trong một văn bản luôn có các khoảng trống, như vậy thử thay các dấu \ bằng các khoảng trống, bản tin thành


{;EADE AFF ,ONEU YO ,U NANL AVVOINY $234567890

Nhận xét tiếp các từ chứa ít ký tự như AFF và YO, trong tiếng Anh, từ 3 ký tự mà hai ký tự sau giống nhau khiến ta nghĩ đến từ ADD và từ 2 ký tự kết thúc bằng O khiến ta nghĩ tới từ TO. Thay vào ta lại được bản tin:


{;EADE ADD ,ONEU TO ,U NANL AVVOINY $234567890

Cho tới đây, dường như ta đã đi được một đoạn đường khá dài để sắp tới đích, thêm vài lần thử người ta có thể tìm ra bản tin.

PLEASE ADD MONEY TO MY BANK ACCOUNT #123456789

Một phương pháp khác để tạo mã mẫu tự đơn có tên là Polybius square. Mẫu tự I và J được kết hợp lại và được xử lý như một từ đơn, để tổng số mẫu tự là 25. 25 mẫu tự lại được chia thành dãy 5x5. Mỗi mẫu tự sẽ được mã bởi một cặp số tương ứng với hàng và cột trong bảng mã







1

2

3

4

5

1

2

3



4

5


A

F

L



Q

V


B

G

M



R

W


C

H

N



S

X


D

IJ

O



T

Y


E

K

P



U

Z

Thí dụ bản văn N O W I S T H E T I M E

33 43 25 42 34 44 32 51 44 42 23 51

3.4.2. Mã đa mẫu tự (Poly-alphabetic cipher) :

Ðể tránh việc lặp lại các ký tự trong bản mật mã, người ta dùng loại mã đa mẫu tự, tương tự mã Caesar, mỗi ký tự cũng được thay bởi một ký tự khác, nhưng các ký tự giống nhau không phải được thay bằng một ký tự duy nhất, mà sẽ được thay bằng các ký tự khác nhau tùy theo vị trí của nó.

Một thí dụ của mã đa mẫu tự là mã Vigenère

Dùng một mãng 2 chiều của các ký tự, trong đó mỗi hàng chứa các mẫu tự theo Alphabet nhưng thứ tự trong từng hàng khác nhau:


Thí dụ:

Cột 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1516 1718 19 20 21 22 23 24 25

Hàng 0 A B CD E FGH I J K L M N O P Q R S T U V W X Y Z

Hàng 1 B C DE FGH I J K L M N O P Q R S T U V W X Y Z A

Hàng 2 C DE F GH I J K L M N O P Q R S T U V W X Y Z A B

Hàng 3 D E FG H I J K L M N O P Q R S T U V W X Y Z A B C



. . . . . . .

. . . . . . .

Hàng 24 Y Z AB C D E FGH I J K L M N O P Q R S T U V W X

Hàng 25 Z AB C D E FGH I J K L M N O P Q R S T U V W X Y

Cột 0 12 3 4 5 6 7 8 9 10 11 12 13 14 1516 17 18 1920 21 22 23 24 25


Ðể thay thế một ký tự, gọi i là vị trí tương đối của nó trong bản tin (bắt đầu là vị trí 0) và j là vị trí tương đối của nó trong thứ tự Alphabet. Gọi V là mảng, ký tự sẽ được thay bằng một ký tự trong V[ i mod 26,j ].

Thí dụ dùng mảng ở trên để thay các chữ THE trong bản tin ở các vị trí 25, 54 và 104. Ta lập bảng thay thế như sau:




Ký tự cần thay

Vị trí i

i mod 26

Vị trí j

Ký tự phải thay

T

H

E



T

H

E



T

H

E



25

26

27



54

55

56



104

105


106

25

0

1



2

3

4



0

1

2



19

7

4



19

7

4



19

7

4



S (h25, kt19)

H (h0, kt7)

F

V

K



I

T

I



G

Như vậy các ký tự THE ở các vị trí khác nhau trong bản tin đã lần lượt được thay bởi SHF, VKI và TIG.

Mặc dù đã giải quyết được sự lặp lại, nhưng xét kỹ chúng ta vẫn thấy rằng có một qui luật mà người ta vẫn có thể nhận ra đó là khoảng cách của các ký tự của cùng một mã là như nhau do tính tuần hoàn của mãng mẫu tự mà chúng ta sử dụng và do bài toán mod 26 (khoảng cách trong mã ASCII của S & H, V & K và T & I đều là 11).

Ðể khắc phục điều này người ta có thể tăng số hàng của mãng ký tự lên, nhưng như vậy đưa đến kết quả là khóa có thể quá dài (thậm chí dài hơn bản tin), khó khăn cho việc phát và lưu trữ một cách an toàn.

3.4.3. Mã chuyển vị (Transposition cipher):

Người ta sẽ sắp xếp lại thứ tự các ký tự của bản văn bằng cách lưu chúng trong một mãng 2 chiều m cột, m ký tự đầu tiên sẽ cho vào hàng thứ nhất, m ký tự kế tiếp cho vào hàng thứ hai, và cứ thế tiếp tục cho hết bản tin, sau đó hoán đổi vị trí các cột theo thứ tự mới, giả sử p1, p2 . . . pm. Sự hoán đổi có thể thực hiện một cách ngẫu nhiên hoặc theo một qui luật định trước. Bản tin sẽ được truyền đi theo thứ tự từ p1, p2 . . . đến pm

Thí dụ bản tin cần phát:

MISS PIGGY KERMIT ANIMAL AND FOZZIE BEAR

Giả sử dùng mãng 5 cột 1 2 3 4 5, Bản tin được đưa vào mãng như sau:

Số cột


1

2

3

4

5

M

P
I


I

A

O



I

I

K



T

M

N



Z

B


S

G

E


A

D

Z



E

S

G

R



A

L
I


A

Y

M



N
F

E

R



Sắp xếp lại các cột theo thứ tự 2, 4, 3, 1, 5, ta được bản tin:

IIKTMNZBSGRAL IASGE ADZEMP IIAO (2 khoảng trống) YMN FER

Rõ ràng là bản tin đã mã hóa không còn một dáng dấp nào của bản tin ban đầu. Nhưng phương pháp vẫn còn khuyết điểm là sự lặp lại của các ký tự. Nếu kẻ gian xác định được mật mã đã dùng là loại chuyển vị thì khả năng giải được mã không khó lắm (nhất là có phương tiện tin học trong tay).

3.4.4. Mã DES (Data Encryption Standard) :

Mã DES được phát triển bởi IBM vào những năm đầu thập niên 70, đã được chính phủ cho phép xem như chuẩn trong việc tạo mật mã dùng trong thương mại và những tin tức không coi là bí mật và người ta đã chế tạo các chip VLSI để thực hiện viêc tạo mã nhanh hơn.

DES chia bản tin ra thành từng khối 64 bit và dùng khóa 56 bit để thực hiện quá trình tạo mã rất phức tạp bao gồm các kỹ thuật như chuyển vị, thay thế, toán tử EX-OR và vài xử lý khác để tạo nên một bản mã 64 bit.

Tiến trình thực hiên gồm:

- Bước 1: Chuyển vị 64 bit dữ liệu và 56 bit khóa

- Bước 2 gồm 16 lần thực hiện sự mã hóa tương tự nhau nhưng với các khóa khác nhau, dữ liệu ra của lần thực hiện trước sẽ là dữ liệu vào của lần thực hiện sau.

- Bước 3: Trộn 32 bit đầu và 32 bit cuối

- Bước 4: Thực hiện lần chuyển vị cuối cùng.

(H 3. 6) mô tả các bước tạo mã của DES



                                                                            (H3.6)

                    (H 3.7) minh họa một trong 16 lần thực hiện mã hóa

Trong (H 3.7) , các ký hiệu C64 chỉ 64 bít đã được mã hóa, L32 chỉ 32 bit đầu của C64, R32 là 32 bít cuối, K56 là khóa 56 bít. Ngoài ra các ký hiệu như X48 chỉ chuỗi dữ liệu 48 bít có được từ một tác vụ trung gian trước đó. Lưu ý là để đơn giản, chúng ta chỉ dùng cùng 1 ký hiệu cho các chuỗi dữ liệu ra của cùng 1 tác vụ, nhưng các chuỗi này là khác nhau (Thí dụ, cùng dùng ký hiệu X6 cho các chuỗi dữ liệu ra từ mạch chia nhóm, nhưng các chuỗi ra từ các mạch khác nhau thì khác nhau).

Như (H 3.7) mô tả, đầu tiên, người ta chia 64 bít ra làm đôi, 32 bít đầu ký hiệu L32 và 32 bít còn lại là R32. Tiếp theo chuỗi R32 được mở rộng thành 48 bít (R48) bằng cách chuyển vị và nhân đôi một số bit (Ta ký hiệu R48 để nhấn mạnh rằng chuỗi này được dẫn xuất từ R32). Ðồng thời khóa 56 bit cũng được phân làm đôi và thực hiện việc quay vòng cho mỗi nhóm (số lần quay tùy theo giải thuật ở từng bước mã hóa khác nhau), sau đó thực hiện chuyển vị, chuỗi bít ra ký hiệu là K56. Bước tiếp theo là thực hiện hàm EX-OR cho R48 và K56, kết quả là chuỗi X48, chuỗi này lại được phân thành 8 nhóm 6 bít (X6) rồi thực hiện việc thay thế để giảm xuống thành các nhóm 4 bít (X4) sau đó tổ hợp 8 nhóm này để thành chuỗi X32. X32 lại được EX-OR với L32, kết quả là X32. Cuối cùng chuỗi X32 tổ hợp với chuỗi bít R32 để cho mã 64 bít (C64).



                                                 

                                                    (H3.7)

Tóm lại, giải thuật để có được một bản tin mật rất là phức tạp, nhưng như thế vẫn chưa chắc đã bảo mật tuyệt đối được bản tin. Ngoài ra, việc qui ước với nhau cách tạo các khóa hoặc cách thông tin cho nhau về các khóa cũng phải được thực hiện sao cho bí mật phải được bảo đảm. Vấn đề bảo mật còn rất nhiều điều phải nghiên cứu.

 

  CHƯƠNG 4



   TRUYỀN NỐI TIẾP BẤT ĐỒNG BỘ

 


. Mục tiêu.

. Kiến thức cơ bản cần có để học chương này.

. Tài liệu tham khảo liên quan đến chương.

. Nội dung:

                4.1  HỆ THỐNG TRUYỀN DỮ LIỆU .

                4.2  MẪU TÍN HIỆU TRONG TRUYỀN BẤT ĐỒNG BỘ .

                4.3 VÀI IC THỰC HIỆN GIAO THỨC BẤT ĐỒNG BỘ .

. Vấn đề nghiên cứu của chương kế tiếp.

        Như đã biết, trong các hệ thống truyền dữ liệu có hai cách đưa tín hiệu lên đường truyền: nối tiếp và song song. Cách truyền song song thường được truyền trên một khoảng cách ngắn, ví dụ giữa các thiết bị trong cùng một phòng như từ máy tính sang máy in.

Cách truyền nối tiếp thường được thực hiện khi khoảng cách truyền khá xa.

Ngoài ra, trong cách truyền nối tiếp, dựa vào cách thực hiện sự đồng bộ giữa nơi phát và thu ta có hai chế độ hoạt động: đồng bộ và bất đồng bộ.

Trong chế độ bất đồng bộ, xung đồng hồ được tạo ra một cách riêng rẻ ở máy phát và máy thu dựa vào tần số danh định tương ứng với vận tốc truyền (bit rate hoặc baud rate).

Trong chế độ đồng bộ, nơi phát có thể gửi xung đồng hồ tới nơi thu theo một kênh truyền song song với kênh truyền dữ liệu hoặc nơi thu tự tạo ra xung đồng hồ bằng cách tách tín hiệu thời gian từ dòng dữ liệu.

Chương này bàn đến chế độ truyền nối tiếp bất đồng bộ. Chúng ta sẽ lần lượt giới thiệu tính chất chung của hệ thống truyền dữ liệu, các giao thức của hệ thống truyền bất đồng bộ. Chúng ta cũng sẽ khảo sát vài IC thực hiện chức năng biến đổi song song, nối tiếp trong các thiết bị thu phát .



  4.1 HỆ THỐNG TRUYỀN DỮ LIỆU:                                                        




1   2   3   4   5   6   7   8   9


Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2019
được sử dụng cho việc quản lý

    Quê hương