HW2 solutions

3.57. An early code used in radio transmission involved using codewords that consist of binary bits and contain the same number of 1s. Thus, the 2-out-of-5 code only transmits blocks of 5 bits in which 2 bits are 1 and the others 0. 

Solutions follow questions: 

a. List the valid codewords. 

11000 
10100 
10010 
10001 
01100 
01010 
01001 
00110 
00101 
00011 

b. Suppose that the code is used to transmit blocks of binary bits. How many bits can be transmitted per codeword? 

There are 10 possible codewords. Three bits per codeword can be transmitted if eight codewords are used. 

c. What pattern does the receiver check to detect errors? 

Each received codeword should have exactly two bits that are ones and three bits that are zeros to be a valid codeword. 

d. What is the minimum number of bit errors that cause a detection failure? 

A valid codeword can be changed into another valid codeword by changing a 1 to a 0 and a 0 to a 1. Therefore, two bit errors can cause a detection failure. 


3.63 Let g1(x) = x + 1 and let g2(x) = x3 + x2 + 1. Consider the information bits (1,1,0,1,1,0). 

a. Find the codeword corresponding to these information bits if g1(x) is used as the generating polynomial. 

Codeword = 1101100 

b. Find the codeword corresponding to these information bits if g2(x) is used as the generating polynomial. 

Codeword = 110110111 

c. Can g2(x) detect single errors? double errors? triple errors? If not, give an example of an error pattern that cannot be detected. 

Single errors can be detected since g2(x) has more than one term. Double errors cannot be detected even though g2(x) is primitive because the codeword length exceeds 2^(n-k) - 1=7. An example of such undetectable error is 1000000010. Triple errors cannot be detected since g2(x) has only three terms. 

d. Find the codeword corresponding to these information bits if g(x) = g1(x) g2(x) is used as the generating polynomial. Comment on the error-detecting capabilities of g(x). 


Codeword = 1101100011 

The new code can detect all single and all odd errors. It cannot detect double errors. It can also detect all bursts of length n – k = 4 or less. All bursts of length 5 are detected except for the burst that equals g(x). The fraction 1/2^(n-k) = 1/16 of all bursts of length greater than 5 are detectable. 


4.10. Suppose a multiplexer has two input streams, each at a nominal rate of 1 Mbps. To accommodate
deviations from the nominal rate, the multiplexer transmits at a rate of 2.2 Mbps as follows. Each
group of 22 bits in the output of the multiplexer contains 18 positions that always carry information
bits, nine from each input. The remaining four positions consist of two flag bits and two data bits.
Each flag bit indicates whether the corresponding data bit carries user information or a stuff bit
because user information was not available at the input.

a. Suppose that the two input lines operate at exactly 1 Mbps. How frequently are the stuff bits
used?

In this case, the stuff bits are always used because the information bits alone only provide an
aggregate bit rate of 1.8 Mbps.

b. How much does this multiplexer allow the input lines to deviate from their nominal rate?

This multiplexer provides either 9 or 10 bits for each stream per 22-bit frame. Thus, it allows
either of the two input streams to transmit as low as 0.9 Mbps and as high as 1.0 Mbps.

4.27. Consider the multistage switch in Figure 4.35 with N = 16, n = 4, k = 2.
Solutions follow questions:
a. What is the maximum number of connections that can be supported at any given time?
Repeat for k = 4 and k = 10.

for k=2,the second stage is the bottleneck, and blocking can occur in the first stage. Thus, eight
connections can be supported at a time.

If k = 4, then blocking will occur if we are not allowed to rearrange connections. It can be shown
that in this case blocking can be avoided if we are allowed to rearrange the connection pattern
every time a new connection request is made.
If k = 10, then there are ten 4 x 4 switches in the second stage. Since there are only 16 inputs
and 16 outputs, the switch can accommodate any set of connections without blocking.

b. For a given set of input-output pairs, is there more than one way to arrange the connections
over the multistage switch?

As in part (a), it is clear that each input-output pair can be connected through
any one of the k second-stage switches. Thus, there are k ways to arrange the connections over
a multi-stage switch.

4.36. Consider the three-stage switch in problem 4.26c. Explain why a space-time-space
implementation of this switch makes sense. Identify the factors that limit the size of the switches that
can be built using this approach.

Solution:
A space-time-space implementation would have the middle stage replaced by a TSI switch stage,
and thus reduce hardware costs. The maximum number of slots in a TSI switch, say M, is limited
by the length of the memory cycle. This limitation means that N/n = M, which in turn places a
limitation on N, the number of inputs to the switch (since n has a maximum that is determined by
technological constraints). The limitation on the number of slots M suggests that the approach is
suitable when concentration can be used in the input stage because of light loading in the input
lines.