Error detecting and correcting codes have become integral to modern communication systems. Shannon provided a beautiful (and non-constructive) proof that tells us that codes exist that can achieve channel capacity. Unfortunately, the best codes have random structure which can make them hard to implement. LDPC codes are considered as good codes for next generation devices, beating out the turbo codes of the past.
I got to learn about LDPC codes and implement a decoder for a simple one… as it turns out these are not only theoretically good but simple to implement. High performance with low complexity is the engineers dream!
The decoder algorithm is the sum-product algorithm. It is an algorithm that can efficiently evaluate the probability that a single bit is correct within the LDPC structure. Since there are many long codewords it is more practical to perform decoding bitwise than by using entire codewords. The algorithm draws its name from the fact that it calculates sums and products for a number of iterations until a decision is made or the decoder fails. The expressions here are from “Efficient Implementations of the Sum-Product Algorithm for Decoding LDPC Codes” by XY Hu et. al., where the notation is also explained in greater detail.
1. The initial step for a received bit (or frame of 155 bits) is to calculate the intrinsic log likelihood ratio. For this we need to know something about the channel in use, which for this report is AWGN. Thus for equiprobable inputs over AWGN channel:
In this initialization step, each check node M(n) is passed intrinsic LLR according to its index position. This value is saved and also put into the messages. Variable nodes are initialized to 0.
2. The second step is to update the variable node messages. For the set N(m) excluding the nth variable node compute the LLRapp by the product equation given. Recall the set N(m) denotes the variable nodes connected to the check node m. For all the rows connected to column m by a 1 in H,
3. The third step is to update the check node messages. For the set M(n) excluding the mth check node calculate the sum as described.
4. The fourth step is to make a decision. This time sum across all the variable node messages and look at the sign of the result. If it is negative output 1, if it is positive output 0. If the resulting sequence passes the parity check, output it. Otherwise return to step 2. If too many iterations have passed and the sequence is still not valid we may declare that the decoder failed.
Since this code has a regular structure it is definitely not optimal. But it is easy to understand.
You could compare the performance I got against other codes and check. This structure is regular and thus the performance is limited.
I can share here the object I made to implement this decoder. Actually, this object could be used to build a decoder for any LDPC code because the structure is instantiated at run time. It’s a MATLAB object, so that makes it pretty easy to implement.
%The object for LDPC decoder. Written by Nicholas Hansen March 2018.
classdef pnode
properties
thisNode = 0;
edge = [0 0 0 0 0];
LLRint = 0;
LLRapp = 0;
sums = [0 0 0];
products = [0 0 0 0 0];
end
methods
function r = addEdge(obj, newedge)
for i=1:1:5
if obj.edge(i) == 0
obj.edge(i) = newedge;
break;
end
end
r = obj.edge;
end
function r = getMess(obj, n)
r = 0;
end
function r = getLLRint(obj, noise, SNR)
variance = 1/(10^(SNR/10));
r = (4*noise)/(variance^2);
%here variance is actually No=2var^2
end
function r = getProduct(obj, checkNodes, j)
product = 1;
F = 0;
for i=1:1:5 %this node's edges
if i ~= j%excluding the current products edge
E=obj.edge(i);
for k=1:1:3%among the sums for that node across the edge
if checkNodes(E).edge(k) == obj.thisNode
%find the sum for this node
F = checkNodes(E).sums(k);
end
end
product = product*tanh(F/2);
end
end
product = 2*atanh(product);
if product > 60 %clipping to avoid large numbers eating up memory
product = 60;
elseif product < -60
product = -60;
end
r = product;
end
function r = getLLRsum(obj, varNodes, j)
F=0;
sum=0;
for i=1:1:3
if i ~= j
E = obj.edge(i);
for k=1:1:5%in the nodes accross the pond
if varNodes(E).edge(k) == obj.thisNode
F = varNodes(E).products(k);
end
end
sum = sum + F;
end
end
r = obj.LLRint + sum;
end
end
end
Serial Engineering 