Hamming codes are block codes, so coded vectors, c, of length n coded bits are formed from a data sequence, d, of length k information bits, and generator matrix, G, as follows:[c] = [G] [d].nx1 nxk kx1There are specific possible sizes of G for hamming codes based ona parameter, m. n = 2m – 1, k = n – m. So, for m = 3, n = 7 andk = 4. This is called the (7,4) Hamming code. Matlab computes the generator as:G = 1 0 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1Remember to do the matrix multiplication modulo-2. Thus, if d = [ 0 0 1 1 ]T, c = Gd mod 2 = [ 2 1 2 0 0 1 1 ]T mod 2= [ 0 1 0 0 0 1 1 ]TAssuming that you pass a large number of bits N >> k, you simply break up the data stream into many kx1 length vectors and encode them in sequence as depicted below:d0, d1, …, d3, d4, d5, … … dN-1[c0[d0 … = G … , C6] d3][c7[d4 … = G … , C13] d7]This yields a long coded sequence of length n/k * N coded symbols:C0, c1, c2, … Cn/k*N-1Because we get k bits of information per n bits of coded data, wehave a code with rate RFEC = k/n = 4/7.Thus, the code data stream will occupy more bandwidth (assuming no pulse shaping or higher order modulation):BWcoded = Rs = Rb / RFEC = 7/4 Rb = 7/4 BWuncoded.That’s an undesirable side effect of adding redundancy, it costs spectrum and can hurt the number of users a system can service. (As an aside, when m = 7, k/n = 120/127 and the bandwidth expansion can be almost negligible. For Hamming codes, this is areasonable way to go, since coding gain is fairly good for high rate codes (RFEC near 1). Generally, choosing a higher rate codegives less coding gain, so high coding rates aren’t always desirable.)We’ll talk more about some alternative decoding approaches, but the Hamming decoding is worth knowing because it is easy to do byhand and easy to ask for on a test. Otherwise, you’ll never use the (7,4) for practical applications—it’s just not powerful enough.Once a data stream is encoded via a block code generator function, you rely on the parity check matrix, H, for the decoding. Basically, the parity check matrix tells you whether all of the added redundancy results in even parity. This will bethe case if there are no errors—but this is not if and only if. If you flip two or more bits in a code block, you may still achieve even parity, but have too many errors to correct per block.To send data through the channel we map 0 -> 1 and 1 -> -1 and then modulate the values. This can be expressed as the transmit sequence, x: x = 1 – 2 * cAs the transmit sequence goes through the channel, we add noise. Thus, our received signal, y, is:y = x + nThe parity matrix operates only on 1s and 0s. So if we received:y = -.5, -.3, -0.7, -1.1, -0.5, 0.3, 1.1, etc,we first perform a hard decoding. Assuming that our mapping was x = 1 – 2 * c, we can use the following hard decision rule:hd = ( y < 0 )This giveshd = 0 0 0 0 0 1 1We check whether this satisfies even parity everywhere as follows:Syndrome = H * hdMatlab gives H as:H = 1 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 0 1 1 1Thus, H * hd = 010This represents the binary number 010bin = 2decimal.The the syndrome location tells us that the second bit in hd needs to be flipped to achieve full even-parity. That could meanthat it will correct a legitimate error. That’s indeed true thistime and gives us a decoded vector:Decoded = 0 flip(0) 0 0 0 1 1= 0 1 0 0 0 1 1= cThe original data is extracted as the last four bits of C:datadecoded = c3 … c6 = [ 0 0 1 1 ] = d.As shown below, encoding shifts our red symbol error rate curve to the right of the uncoded bit error rate curve (theory), because Es = RFEC x Eb < Eb.However, the BER benefit due to the Hamming code more than compensates for this and puts the hamming BER to the left of bothcurves. The dB EbNo benefit of the decoding relative to an uncoded BER is called the coding gain. It’s rather modest in this example but much larger for good codes. Note, that coding gain is defined for a particular BER and is different at different BER levels.BER4 6 8 10 1210-610-510-410-310-210-1 theorysymbol error ratehamming BEREb/NoThe process in summary is:c = Gdx = 1 – 2cy = x + nhd = y < 00.6 dB coding gain@ m = 3syn = H hddecoded = flip a bit at syn_location in hd if syn is not zero.Extract data from decoded by discarding parity