# 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 = *j*(len(SubMatrix))+SubMatrix[i]+[random.randint(0,1)
for k in range((j+1)*len(SubMatrix), Length*len(SubMatrix))]
G.append(row)
return G

def Encode(Sequence, Generator):
Codeword = []
for i in range(0, len(Generator)):
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*(len(Sequence)/Rate-1), Rate*len(Sequence)/Rate):
Parity = 0
for j in range(0,len(Sequence)):
Parity ^= Generator[j][i]&Sequence[j]
Metric += (Codeword[i]^Parity)*FanoMetrics + (Codeword[i]^Parity^1)*FanoMetrics
return Metric

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


An example using the code above


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)]

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.