A commonly used algorithm for sequential decoding is the stack algorithm. It was invented by Zigangirov and Jelinek in the 60’s. The algorithm is a depth-first algorithm with non-deterministic complexity:

Algorithm (Stack algorithm)

1. Put the root node in the list .
2. Remove top node. Place its successors in . Sort in (Fano) metric order.
3. If top path leads to end of tree, stop and output the path as decoded codeword. Otherwise, go to Step 2.

import random
import bisect
import itertools
from math import log

def CreateGeneratorMatrix(SubMatrix, Length):
	G = []
	for j in range(0,Length):
		for i in range(0,len(SubMatrix)):
			row = [0]*j*(len(SubMatrix[0]))+SubMatrix[i]+[random.randint(0,1)
			for k in range((j+1)*len(SubMatrix[0]), Length*len(SubMatrix[0]))]
			G.append(row)
	return G

def Encode(Sequence, Generator):
	Codeword = []
	for i in range(0, len(Generator[0])):
		Parity = 0
		for j in range(0,len(Sequence)):
			Parity ^= Generator[j][i]&Sequence[j]
		Codeword.append(Parity)
	return Codeword
	
def Metric(Sequence, Codeword, Generator, Rate, FanoMetrics):
	Metric = 0
	for i in range(Rate[1]*(len(Sequence)/Rate[0]-1), Rate[1]*len(Sequence)/Rate[0]):
		Parity = 0
		for j in range(0,len(Sequence)):
			Parity ^= Generator[j][i]&Sequence[j]
		Metric += (Codeword[i]^Parity)*FanoMetrics[1] + (Codeword[i]^Parity^1)*FanoMetrics[0]
	return Metric
	
def Decode(Codeword, Generator, Rate, ErrorProbability):
	Permutations = [list(seq) for seq in itertools.product([0,1], repeat=Rate[0])]
	Stack = []
	FanoMetrics = [log(1-ErrorProbability, 2)+(1-Rate[1]/Rate[0]), log(ErrorProbability, 2)+ (1-Rate[1]/Rate[0])]
	for Permutation in Permutations:
		bisect.insort(Stack,[Metric(Permutation, Codeword, Generator, Rate, FanoMetrics), Permutation])
	while(len(Stack[0][1]) < len(Generator)):
		BestSequence = Stack.pop(0)
		for Permutation in Permutations:
			bisect.insort(Stack, [BestSequence[0]+Metric(BestSequence[1]+Permutation, 
			Codeword, Generator, Rate, FanoMetrics), BestSequence[1]+Permutation])
		while len(Stack) > 100:
			Stack.pop(0)
	return Stack.pop()[1]

An example using the code above

def AddErrors(Message, Weight):
	for index in map(int,(sample(xrange(len(Message)),Weight))):
		Message[index] ^= 1
	return Message

SubMatrix = [[1,0,1],[0,1,1]]
G = CreateGeneratorMatrix(SubMatrix,15)

Message = [random.randint(0,1) for k in range(0,len(SubMatrix)*15)]
Codeword = AddErrors(Encode(Message, G),3)

print Decode(Codeword, G, [2,3])

where we create random time-varying rate convolutional code with infinite memory and generate a random message. Then we add two errors to some arbitrary positions and decode.

The code is slow, but shows the general idea.