# This is the template file for Lab #4, Task #3 import numpy,sys import lab4 class ViterbiDecoder: # Given the constraint length and a list of parity generator # functions, do the initial set up for the decoder. The # following useful instance variables are created: # self.K # self.nstates # self.r # self.predecessor_states # self.expected_parity def __init__(self, K, glist): self.K = K # constraint length self.nstates = 2**(K-1) # number of states in state machine # number of parity bits transmitted for each message bit self.r = len(glist) # States are named using (K-1)-bit integers in the range 0 to # nstates-1. The bit representation of the integer corresponds # to state label in the transition diagram. So state 10 is # named with the integer 2, state 00 is named with the # integer 0. # for each state s, figure out the two states in the diagram # that have transitions ending at state s. Record these two # states as a two-element tuple. self.predecessor_states = \ [((2*s+0) % self.nstates,(2*s+1) % self.nstates) for s in xrange(self.nstates)] # this is a 2D table implemented as a list of lists. # self.expected_parity[s1][s2] returns the r-bit sequence # of parity bits the encoder transmitted when make the # state transition from s1 to s2. self.expected_parity = \ [[lab4.expected_parity(s1, s2, K, glist) \ if s1 in self.predecessor_states[s2] else None for s2 in xrange(self.nstates)] for s1 in xrange(self.nstates)] # expected is an r-element list of the expected parity bits. # received is an r-element list of actual sampled voltages for the # incoming parity bits. This is a hard-decision branch metric, # so, as described in lab write up, digitize the received voltages # to get bits and then compute the Hamming distance between the # expected sequence and the received sequence, return that as the # branch metric. Consider using lab4.hamming(seq1,seq2) which # computes the Hamming distance between two binary sequences. def branch_metric(self,expected,received): # your code here... pass # Compute self.PM[...,n] from the batch of r parity bits and the # path metrics for self.PM[...,n-1] computed on the previous # iteration. Consult the method described in the lab write up. # In addition to making an entry for self.PM[n,s] for each state # s, keep track of the most-likely predecessor for each state in # the self.Predecessor array (a two-dimensional array indexed by s # and n). You'll probably find the following instance variables # and methods useful: self.predecessor_states, self.expected_parity, # and self.branch_metric(). To see what these mean, scan through the # code above. def viterbi_step(self,n,received_voltages): # your code here... pass # Identify the most-likely ending state of the encoder by # finding the state s that has the minimum value of PM[s,n] # where n points to the last column of the trellis. If there # are several states with the same minimum value, choose one # arbitrarily. Return the tuple (s,n). def most_likely_state(self,n): # your code here... pass # Starting at state s at time n, use the Predecessor # array to find all the states on the most-likely # path (in reverse order since we're tracing back through # the trellis). Each state contributes a message bit. # Return the decoded message as a sequence of 0's and 1's. def traceback(self,s,n): # your code here... pass # Figure out what the transmitter sent from info in the # received voltages. def decode(self,received_voltages,debug=False): # figure out how many columns are in the trellis nreceived = len(received_voltages) max_n = (nreceived/2) + 1 # this is the path metric trellis itself, organized as a # 2D array: rows are the states, columns are the time points. # PM[s,n] is the metric for the most-likely path through the # trellis arriving at state s at time n. self.PM = numpy.zeros((self.nstates,max_n),dtype=numpy.float) # at time 0, the starting state is the most likely, the other # states are "infinitely" worse. self.PM[1:self.nstates,0] = 1000000 # a 2D array: rows are the states, columns are the time # points, contents indicate the predecessor state for each # current state. self.Predecessor = numpy.zeros((self.nstates,max_n), dtype=numpy.int) # use the Viterbi algorithm to compute PM # incrementally from the received parity bits. n = 0 for i in xrange(0,nreceived,self.r): n += 1 # Fill in the next columns of PM, Predecessor based # on info in the next r incoming parity bits self.viterbi_step(n,received_voltages[i:i+self.r]) # print out what was just added to the trellis state if debug: print self.PM[:,n],self.Predecessor[:,n] # find the most-likely ending state from the last row # of the trellis s,n = self.most_likely_state(n) # reconstruct message by tracing the most likely path # back through the matrix using self.Predecessor. return self.traceback(s,n) # print out final path metrics def dump_state(self): print self.PM[:,-1] if __name__=='__main__': K = 3; glist = (7,6) d = ViterbiDecoder(K, glist) message = [1,0,1,0,1,1,0,0] received = lab4.convolutional_encoder(message, K, glist) i = 0 print 'TEST', i decoded = numpy.array(d.decode(received, debug=True)) print 'Testing without adding noise...' if (message == decoded).all() == True: print 'Successfully decoded no-noise Test 0: congratulations!' print else: print 'Oops... error in decoding no-noise Test', i print 'Decoded as ', decoded print 'Correct is', message sys.exit(1) nbits = 29 message = numpy.random.random_integers(0,1,nbits) for (K, glist) in ((3, (7,6)), (4, (0xD,0xE))): i = i + 1 print 'TEST', i d = ViterbiDecoder(K, glist) received = lab4.convolutional_encoder(message, K, glist) decoded = numpy.array(d.decode(received, debug=True)) if (message == decoded).all() == True: print 'Successfully decoded no-noise Test', i, ': congratulations!' print else: print 'Oops... error in decoding no-noise Test', i print 'Decoded as', decoded print 'Correct is', message sys.exit(1) # When ready for checkoff, enable the following line. #lab4.checkoff(ViterbiDecoder,task='L4_3',debug=False)