Question: Consider the coding and decoding functions E and D defined in Example

Question

Question: Consider the coding and decoding functions E and D defined in Example 7.1.9. (* Include a value E(x) and D(x) that indicates an error.)

a. Find E(0110) and D(111111000111).

b. Find E(1010) and D(000000111111)

Example 7.1.9

Digital messages consist of finite sequences of 0’s and 1’s. When they are communicated across a transmission channel, they are frequently coded in special ways to reduce the possibility that they will be garbled by interfering noise in the transmission lines. For example, suppose a message consists of a sequence of 0’s and 1’s. A simple way to encode the message is to write each bit three times. Thus the message

00101111

would be encoded as

000000111000111111111111.

The receiver of the message decodes it by replacing each section of three identical bits by the one bit to which all three are equal.

Let A be the set of all strings of 0’s and 1’s, and let T be the set of all strings of 0’s and 1’s that consist of consecutive triples of identical bits. The encoding and decoding processes described above are actually functions from A to T and from T to A. The encoding function E is the function from A to T defined as follows: For each string s A,

E(s) = the string obtained from s by replacing each bit of s by the same bit written three times.

The decoding function D is defined as follows: For each string t T ,

D(t) = the string obtained from t by replacing each consecutive triple of three identical bits of t by a single copy of that bit.

The advantage of this particular coding scheme is that it makes it possible to do a certain amount of error correction when interference in the transmission channels has introduced errors into the stream of bits. If the receiver of the coded message observes that one of the sections of three consecutive bits that should be identical does not consist of identical bits, then one bit differs from the other two. In this case, if errors are rare, it is likely that the single bit that is different is the one in error, and this bit is changed to agree with the other two before decoding

Explanation / Answer

Solution :-

The function E denotes for encoding and D for decoding function.

a) Find E(0110) and D(111111000111)

The function E encode the given string by put three identical bits in place of single bit.

E(0110) = 000111111000

Now we include an error bit in the function.

E(0110) = 010111111000

The underlined bit is error bit that it is not identical in the first triplet. So it is changed that it will agree with the remaining two bits and all three bits becomes identical in the triplet.

D(111111000111) = 1101

Now we demonstrate the error in this function.

D(111101000111) = 1101

The underlined bit is error bit and it is not identical with other bits in the triplet. So this bit is changed and the all bit became identical in the triplet. And the result will be correct.

b) Find E(1010) and D(000000111111)

The function E encodes the given string by putting the three identical bits in place of single bit.

E(1010) = 111000111000

Now we include an error bit in the function.

E(1010) = 111010111000

The underlined bit is error bit that is not identical in the second triplet. So it is changed that is it will agree with other bits in the triplet and all three bits become identical in the triplet.

D(000000111111) = 0011

Now we demonstrate the error bit in this function.

D(000010111111) = 0011

The underlined bit is error bit that is not identical in the triplet. This bit is changed that it will agree with other bits in the triplet and all the bits in the triplet become identical. The result will correct.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.