In the 4B/5B encoding scheme, every 4 bits of data are encoded in a 5bit codeword. It is required that the codewords haveat most 1 leading and at most 1 trailing zero. How many such codewords are possible?
Answer is (C)
It says we have 5 bit codeword such that "it can't have two consecutive zeros in first and second bit" and
also" can't have two consecutive zeros in last two bits.
Code word with first two bits zero = 00xxx =8
Code word with last two bits zero = xxx00 =8
Code word with first and last two bits zero = 00x00 =2
Code word with first OR last two bits zero = 8+82=14
Therefore possible codewords =3214 =18
Consider a 3bit error detection and 1bit error correction hamming code for 4bit datq. The extra parity bits required would be ___ and the 3bit error detection is possible because the code has a minimum distance of ____
The Hamming distance between two bit strings is the number of bits that would have to flip to make the strings identical.
To detect d errors requires a minimum Hamming distance of d + 1 .
Correcting d bit flips requires a minimum Hamming distance of 2 * d + 1 , where d is number of bit in errors .
For the first blank , each error detection we need 1 parity bit
for 3 bit error detection we need 3 parity bit ...... So, 3 parity bit requires here. answer is 3.
Also we can calculate this way, formula is d+p+1 <= 2p where d=data bits , p = parity bits , d=4 bit given.
according to 1st question, d= 4 so 4+p+1<= 2p
p+5 <= 2p now if p=2 it becomes 7 <= 4 , Not satisfy . p = 3 it becomes 8 <= 8 , satisfy.
so p must be 3 .[ Minimum value of p is 3 ]
The second blank the 3bit error detection is possible because the code has a minimum distance of ____ answer is
3+1=4, where d=3. Formula used d+1.
Answer for 2 blanks are [ 3,4 ]
In a communication network, a packet of length L bits takes link L_{1}with a probability of P1 or link L_{2 }with a probability of P_{2}. Link L_{1} and L_{2} have bit error probability of b_{1} and b_{2} respectively. The probability that the packet will be received without error via either L_{1} or L_{2 }is
Probability of choosing link L_{1}
= P_{1}
Probability for no bit error (for any single bit) = 1  b_{1}
Similarly for link L_{2}
Probability of no bit error = (1  b_{2})
Packet can go either through link L_{1 }or L_{2 }they are mutually exclusive events (means one event happens other won't be
happening and so we can simply add their respective probabilities for the favorable case).
Probability packet will be received without any error = Probability of L_{1 }being chosen and no error in any of the L bits +
Probability of L_{2} being chosen and no error in any of the L bits
Hence answer is option A .
Why option D is not correct choice here ?
Option D here is giving the probability of a frame being arrived with at least one bit correctly  i.., all the bits are not
errors.
An error correcting code has the following code words: 00000000, 00001111, 01010101, 10101010, 11110000. What is themaximum number of bit errors that can be corrected?
Answer: B
For correction: Floor of [(Hamming Distance  1)/2] = Floor of [1.5] = 1 bit error.
For detection: Hamming Distance  1 = 3 bit error.
Data transmitted on a link uses the following 2D parity scheme for error detection:
Each sequence of 28 bits is arranged in a 4x7 matrix (rows r_{0 }through r_{3}, and columns d_{7 }through d_{1} ) and is padded witha column d_{0 }and row r_{4 }of parity bits computed using the Even parity scheme. Each bit of column d_{0} (respectively, row r_{4} ) gives the parity of the corresponding row (respectively, column). These 40 bits are transmitted over the data link.
The table shows data received by a receiver and has corrupted bits. What is the mini mum possible value of ?
Here we need t o change minmum 3 bits, so by doing it correct we get correct parity column wise and row wise (Correction
marked by dark number).
C is answer
Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?
Let me first explain building blocks to this problem. Before answering this, we should know the relationship between Sent
codeword, Received codeword, CRC generator and error polynomial.
let's take an example:
Sent codeword = 10010 (=x^{4}+x)
Received codeword = 10110 (error at 2nd bit ) (=x^{4}+x^{2}+x)
GATE Overflow September 2017 161 of 740
Now, i can write Sent codeword = Received codeword + error (10010 = 10110 + 00100, here we do modulo 2
arithmetic i.e 1+1 =0 without carry )
in polynomial also we can see x^{4}+x = x^{4}+x^{2}+x+x^{2} = x^{4}+2x^{2}+x = x^{4}+x (here multiplier with 2 means 0 bcoz it
coressopnds to binary modulo 2 arithmetic which is 1+1 = 0 (not 2) )
or
We can also write Received codeword = Sent codeword + error (Check it using same mrthod as above)
Sent codeword C(x), Received codeword R(x) and error E(x).
Now we have R(x) = C(x) + E(x). and let CRC polynomial be G(x). G(x) always divides C(x), and if there is an error then
G(x) should not divide R(x). Lets check 
R(x) mod G(x) =(C(x) + E(x)) mod G(x) (for simplicity i am writing mod as division )
If G(x) divides E(x) also this would mean G(x) divides R(x). We know that, If G(x) does not properly divide R(x) then there
is an error but we are never sure if there is error or not when G(x) divides R(X).
As we saw, G(x) divides R(x) or not totally depends on G(x) divides E(x) or not. whole strength of G(x) lies if it does not
divide any possible E(x).
Lets see again E(x). if there is an error in 3rd and 4th bit from left (LSb is 0th bit ) then E(X) = x4+x3.( it does not matter
error is from toggling 1 to 0 or 0 to 1) Check with above example.
Now come to question. it says G(x) should detect odd number of bits in error?. If number of bits are odd then terms in E(x)
would be odd.
for instance if 1st, 2nd and 5th bit got corrupted then E(x) = x^{5}+x^{2}+x.
It is clear that if any function f(x) has a factor of xk, then at x=k, f(x) would be zero. I.e.f(x) = 0 at x=k.
E(x) must contain an odd number of terms with coefficients equal to 1.
Option C.
A layer4 firewall (a device that can look at all protocol headers up to the transport layer) CANNOT
Answer is (D).
(A) It is POSSIBLE to block "entire" HTTP traffic by blocking all the traffic on port number 80 Since here we DON'T need to check anything that is application layer specific. We only need to block port no 80 for
required time span.
(B) & (C) are fairly possible to achieve.
(D) However (D) is not possible to achieve although the service uses TCP at transport layer. But see the question. We dont need to block entire TCP traffic so we cant block any specific PORT number. Also it is given
that IT IS MULTI USER System and so many user may be using same port for communication. Therefore blocking that port would block all the users WHILE we want a specific user. So how to do that. To do so we
need Application layer specific information of the user like user_id type of things which cant be checked as it is 4layer firewall.
So it is not possible to allow other users and block some specific at the same time using a 4layer firewall (unless they all be using different port numbers which we actually cant predict).
Following 7 bit single error correcting hamming coded message is received.
Determine if the message is correct (assuming that at most 1 bit could be corrupted). If the message contains an error find the bit which is erroneous and gives correct message.
There is error in This message. Error is in bit 6.
How to calculate it ? First of all reverse given input to get it in correct position from 1 to 7.
0110001
Bit 1, Bit 2 & Bit 4 are partity bits.
Calculating position of error =>
c3 c2 c1
1 1 0
Here c1 = bit4⊕bit5⊕bit6⊕bit7=0⊕0⊕0⊕1=1 (Taking Even parity )
c2 = bit2⊕bit3⊕bit6⊕bit7=1⊕1⊕0⊕1=1
c3 = bit1⊕bit3⊕bit5⊕bit7=0⊕1⊕0⊕1=0
Hamming%287,4%29
When you correct bit 6 .
You get message as 0110011.
IF you calculate C1,c2,c3 all will be 0 now !
A message is made up entirely of characters from the set x = {P,Q,R,S,T} . The table of probabilities for each of the characters is shown below:
Total 1.00
If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message
in bits is ______.
What is the distance of the following code 000000, 010101, 000111, 011001, 111111?
Distance (also called mindistance) of a block code is the minimum number of positions in which any two distinct codes
differ. Here, mindistance occurs for the codes 2 and 3 and they differ only in 2 positions. So, d = 2.
Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 




