bilangan 6

CHAPTER 6: CODING

6.1: Coding of Binary Information
6.2: Cryptography

6.1 CODING OF BINARY INFORMATION

 The basic unit of information, called a message, is a finite sequence of characters from a finite alphabet. We shall choose the alphabet set B = . Every character or symbol that we want to transmit is now represented as a sequence of m elements from B. That is, every character or symbol is represented in binary form.

 A word is a sequence of m 0’s and 1’s.

 An element in Bm will be written as (b1, b2, b3, …, bm) or more simply as b1b2b3…bm. Observe that Bm has 2m elements.

 The following figure shows the basic process of sending a word from one point to another point over a transmission channel.








An element is sent through the transmission channel and received as an element .In actual practice, the transmission channel may suffer disturbances, which are generally called noise, due to the weather interference, electrical problems, and so on, that may cause a 0 to be received as a 1, or vice versa. This erroneous transmission of digits in a word being sent may give rise to situation where the word received is different from the word that was sent; that is, x xt. If an error does occur, then xt could be any element of Bm.










 The basic task in the transmission of information is to reduce the likelihood of receiving a word that differs from the word that was sent. This is done as follows.
 We first choose an integer n > m and one-to-one function e: Bm Bn. The function e is called an (m, n) encoding function, and we view it as a means of representing every word in Bm as a word in Bn. If b Bm, then e(b) is called the code word representing b. The additional 0’s and 1’s can provide the means to detect or correct errors produced in the transmission channel.
So, now we transmit the code words by means of a transmission channel. Then each code word x = e(b) is received as the word xt in Bn. This situation can be defined in the following figure.

e

 We need to have an encoding function e to be one to one so that different words in Bm will be assigned different code words.

 If the transmission channel is noiseless, then xt = x for all x in Bn. In this case
x = e(b) is received for each b , and since e is a known function, b may be identified.

 In general, errors in transmission do occur. We will say that the code word
x = e (b) has been transmitted with k or fewer errors if x and xt differ in at least 1 but not more than k positions.

 For x Bn, the number of 1’s in x is called the weight of x and is denoted by .

Example 1:
Find the weight of the given words:
(a) 1011 (b) 0110 (c) 1110 (d) 011101
(e) 111111 (f) 010101
Solution:




Example 2:
Find the weight of each of the following words in B8:
(i) 10101010.
(ii) 11011001.
Solution:


Parity Check Code:

The following encoding function e : Bm is called the parity (m, m+1) check code: If b = b1b2…..bm ,define
e(b) = b1b2…..bmbm+1
where

Observe that bm+1 is zero if and only if the number of 1’s in b is even number. It then follows that every code word e(b) has even weight. A single error in the transmission of a code word will change the received word to a word of odd weight and therefore can be detected. In the same way we see that any odd number of errors can be detected.

For a concrete illustration of this encoding function, let m = 3. Then



Suppose now that b = 111. Then x = e(b) = 1111. If the transmission channel transmits x as xt = 1101, then |xt| = 3, and we know that an odd number of errors (at least one) has occurred.

It should be noted that if the received word has even weight, then we cannot conclude that the code word was transmitted correctly, since this encoding function does not detect an even number of errors. Despite this limitation, then parity check code is widely used.

Example 3:
Consider the (7, 8) parity check code. For each of the received word, determine whether an error
will be detected.
(i) 11001011,
(ii) 01100101.
Solution:




Example 4:
Consider the (7, 8) parity check code. For each of the received words, determine whether an
error will be detected.
(i) 00101101.
(ii) 11111000.
Solution:





How are we going to correct the errors once it is detected?

Now consider the Venn Diagram associated with three sets A, B and C. There are seven compartments numbered 1 through 7 as shown below.



Suppose that you have a four bits information or word, say 1100 to transmit from one point to another. We shall prepare the four bits for transmission by placing them in the first four compartments of the Venn diagrams shown below.




We then fill the remaining three compartments with what are called parity check bits. The rule for generating parity check bits is that the total number of 1’s in each of the three sets A, B, and C must be even. For example, in set A, the parity check bit in compartment 5 is 0 because there are already two 1’s. Similarly the parity bit in the compartments 6 and 7are 1 and 0 respectively. Thus for a completed process each of the seven compartments will contain one bit: four bits are information bits and three are parity bits as shown below.



Now, we transmit the code word 1100010 to the desired destination. Suppose the code word is garbled in transmission and you received 1110010. The receiver can detect and correct this error using the decoding algorithm.
The first step is to place the seven received bits back into the seven apartments as shown below.


The decoder then rechecks the three parity bits. For this case, there is an error in set A since it contain three 1’s; set B also has an error but set C is ok. The conclusion is that an error occurs in , that is in compartment 3. So the decoder changes the bit in compartment 3 from 1 to 0 and decides that the transmitted word is 1100.

Note that this procedure will locate any single error, even if it occurs in one of the parity locations. However if two or more errors occur, this procedure will fail. For this reason the procedure is called single-error correcting code.

Beside three sets in a Venn Diagram, we can also have four sets A, B, C and D giving you a 15 bits code word, of which 11 are data and 4 are parity check. The procedure of encoding and decoding can be further generalized to produce 31 bits, 63 bits, 127 bits, and 255 bits code word. Of course, it will be difficult to work with these codes by hand, but they can easily be implements on a computer.

Example 5:
A word is encoded using the parity check code and it is transmitted. For the following received
word, decode the word using a single-error correcting code procedure.
0110110
Solution:











Example 6:
A word is encoded using the parity check code and it is transmitted. For each of the following
received words, decode the words using a single-error correcting code procedure.
(i) 1010101.
(ii) 1100101.
Solution:


















Other Common Encoding Function

Consider the following (m, 3m) encoding function e: Bm . If
b = b1b2…bm Bm,
define
e(b) = e(b1b2…bm) = b1b2…bmb1b2…bmb1b2…bm.

That is, the encoding function e repeats each word of Bm three times. For a concrete example, let m = 3. Then



Decoding and Error Correction

Consider the following decoding function d: B3m . Let
y = y1y2…ymym+1…y2my2m+1…y3m.
Then
d(y) = z1z2…zm,
where


That is, the decoding function d examines the i th digit in each of the three blocks transmitted. The digit that occurs at least twice in these three blocks is chosen as the decoded i th digit.

Suppose now that b = 011. Then e(011) = . Assume now that the transmission channel makes an error in the underlined digit and that we receive the word 011111011. Then, since the first digits in two out of the three blocks are 0, the first digit is decoded as 0. Similarly, the second digit is decoded as 1, since all three second digits in the three blocks are 1. Finally, the third digit is also decoded as 1, for the analogous reason. Hence, the decoded word is 011, which is the word that was sent. Therefore, the single error has been corrected. A similar analysis shows that, if e is this (m, 3m) code for any value of m and d is as defined, then (e, d) corrects any single error.



Hamming Distance

Let x and y be words in Bm. The hamming distance between x and y is the weight, , of . Thus the distance between x = x1x2…….xm and y = y1y2….ym is the number of values of i such that xi yi, that is, the number of positions in which x and y differ. Using the weight of is a convenient way to count the number of different positions.

Example 7:
Find the distance between x and y:
(a) x = 00111001, y = 10101001
(b) x = 11010010, y = 00100111
Solution:









Properties of The Distance Function

Let x, y and z be elements of Bm. Then,
(a)
(b)
(c)
(d)


Minimum Distance

The minimum distance of an encoding function e : is the minimum of the distances between all distinct pairs of code words; that is

min









Example 8:
Consider the following (2,5) encoding function e:


Find the minimum distance for the above encoding function.
Solution:















Example 9:
Consider the following (2,4) encoding function e:
e(00) = 0000
e(10) = 0101
e(01) = 0110
e(11) = 1111
Find the minimum distance.
Solution:













Note: An (m, n) encoding function e : can detect k or fewer errors if and only if its minimum distance is at least k +1.

Example 10:
Consider the (3,8 ) encoding function e : defined by


How many errors will e detect?
Solution:
Here the minimum distance is 3, as can be checked by computing the minimum of the distance between all 28 distinct pairs of code words. From the above note, since the minimum distance is 3, we have . Thus the code will detect two or fewer errors.

Example 11:
Consider the (2, 8) encoding function e:
e (00) = 00000000
e (01) = 01110010
e (10) = 10011100
e (11) = 01100101
(i) Find the minimum distance of e.
(ii) How many errors will e detect?
Solution:















Example 12:
Consider the (2, 6) encoding function e:
e(00) = 000000
e(01) = 100101
e(10) = 001100
e(11) = 111011
(i) Find the minimum distance of e.
(ii) How many errors will e detect?
Solution:





































6.2 Cryptography

Cryptography (Cryptology) is the study of systems, called cryptosystems, for secure communications. In a cryptosystem, the sender transforms the message before transmitting it so that, hopefully, only authorized recipients can reconstruct the original message (i.e. the message before it was transformed). The sender is said to be encrypt the message, and the recipient is said to decrypt the message. If the cryptosystem is secure, unauthorized persons will be unable to discover the decryption techniques, so even if they are read the encrypted message, they will be unable to decrypt it. Cryptosystems are important for large organizations (e.g., government) as well as for individuals.

In one of the oldest and simplest systems, the sender and receiver each have a key that defines a substitute character for each potential character to be sent. Moreover, the sender and receiver do not disclose the key. Such keys are said to be private.

Example 1:
If a key is defined as

character A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
replaced by E I J F U A X V H W P G S R K O B T Q Y D M L Z N C

the message SEND MONEY would be encrypted as QARUESKRAN. The encrypted message SKRANEKRELIN would be decrypted as ???



In private key cryptosystems, we use congruence to encrypt the messages. According to this, the messages, which are strings of characters, are translated into numbers. Then the number of each character is transformed into another number, either using a shift or, an affined transformation modulo 26.

One of the earliest known user of cryptology was by Julius Caesar.

For example:

When a shift cipher is used with encryption key k, a number p representing a letter is sent as
c = (p +k) mod 26

Decryption is carried out by shifting by –k; that is
p = (c-k) mod 26






Example 2:
What is the secret message produced from the message “MEET YOU IN THE PARK” using the Caesar cipher with K = 3?

Solution:
First replace the letters in the message with numbers. This produces


Now replace each of these numbers p by c=(p+3) mod 26. This gives


Translating this back to letters produces the encrypted message
“PHHW BRX LQ WKH SDUN”


When a private key cryptosystem is used, pair of people who wish to communicate in secret must have a separate key. Since anyone knowing this key can both encrypt and decrypt message easily. These two people need to securely exchange the key.


Example 3:
Using Caesar cipher with K = 1, what is the cipher text for this plain text “ATTACK AT DAWN”
Solution:






















The RSA Public-Key Cryptosystem
 In the RSA system, each participant makes public an encryption key and hides a decryption key.

 To send a message, all one needs to do is look up the recipient’s encryption key in a publicly distributed table. The recipient then decrypts the message using the hidden decryption key.

 In the RSA system, messages are represented as numbers.
For example, each character might be represented as a number. If blank is represented as 1, A as 2, B as 3, and so on, the message SEND MONEY would be represented as 20061505011416150626.

 Each prospective recipient chooses two primes p and q and computes z = pq. Next, the prospective recipient chooses an integer n. The pair z, n is then made public. Finally, the prospective recipient computes the unique number s and the number s is kept secret and used to decrypt messages.

 To send the integer a, 0 z-1, to the holder of public key z, n, the sender computes c = an mod z and sent c. To decrypt the message, the recipient computes cs mod z, which can be shown to be equal to a.

 It may appear that huge numbers must be computed in order to encrypt and decrypt messages using the RSA system. The key to simplifying the computation is to note that the arithmetic is done mod z. It can be shown that
ab mod z = [(a mod z) (b mod z)] mod z

Example 4:
In the RSA public-key cryptosystem, to encrypt a, compute c = an mod z and send c to the holder of the public keys z and n, where z is chosen as the product of two primes p and q. Assume that we choose our primes to be p = 59 and q = 101, and n = 41, encrypt 584 using the public keys z and n.
Solution:













Example 5:
In the RSA public-key cryptosystem, to encrypt a, compute c = an mod z and send c to the holder of public keys z and n, where z is chosen as the product of two primes p and q. Assume that we choose our primes to be p = 37 and q = 31, and n = 28, encrypt 999 using the public keys z and n.
Solution:



















Example 6:
In the RSA public-key cryptosystem, to encrypt a, compute c = an mod z and send c to the holder of public keys z and n, where z is chosen as the product of two primes p and q. Assume that we choose our primes to be p = 17 and q = 23, and n = 11, encrypt 343 using the public keys z and n.
Solution: