Stack algorithm in Python

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 \mathcal{S}.
  2. Remove top node. Place its successors in \mathcal{S}. Sort \mathcal{S} 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.
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 R = 2/3 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s