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)
- Put the root node in the list
.
- Remove top node. Place its successors in
. Sort
in (Fano) metric order.
- If top path leads to end of tree, stop and output the path as decoded codeword. Otherwise, go to Step 2.
This Python code does the job (using an infinite stack which is OK for smaller instances):
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.