SISO vector decoder for IRA-LDPC codes in VHDL

Quick start

Prerequisites:

• GHDL to simulate VHDL.
• GNU Make to use the Makefile for building.
• GTKWave to view the waveforms generated by the simulation.
• C++ compiler to build the test vector generators.

Run make vector to build and simulate vector versions of the check node processor and decoder.

Compare resulting cnp_vector_tb_out.txt with cnp_vector_tb_exp.txt for the check node processor.

Compare resulting dec_vector_tb_out.txt with dec_vector_tb_exp.txt for the decoder.

Scalar versions for studying

Run make scalar to build and simulate scalar versions of the check node processor and decoder.

Compare resulting cnp_scalar_tb_out.txt with cnp_scalar_tb_exp.txt for the check node processor.

Compare resulting dec_scalar_tb_out.txt with dec_scalar_tb_exp.txt for the decoder.

Run make vcd to generate scalar version waveforms and watch them via gtkwave cnp_scalar_tb.vcd.

Adding new scalar code tables

Checkout tables for suitable code tables.

Store new table in table_scalar.txt while making sure that the constants in ldpc_scalar.vhd and ldpc_scalar.hh match.

Run make scalar to see if the new table is free from data hazards by comparing dec_scalar_tb_out.txt with dec_scalar_tb_exp.txt.

Adding new vector code tables

Checkout tables for suitable code tables.

Store new table in table_vector.txt while making sure that the constants in ldpc_scalar.vhd, ldpc_vector.vhd, ldpc_scalar.hh and ldpc_vector.hh match.

Run make vector to see if the new table is free from data hazards by comparing dec_vector_tb_out.txt with dec_vector_tb_exp.txt.

TODO

• Interface for switching or replacing code table
• Shortening the pipeline if timing analysis allows it
• More corner case testing and documentation
• Can the interface be improved?

DONE

• Self-Corrected Min-Sum
• Scalar and Vector versions
• Min-Sum or Offset-Min-Sum with fixed beta = 1
• Pipelined processing
• Write disable flags to resolve write conflicts with DDSMs
• Reference decoder in C++
• Tool for checking code table entries for data hazards
• Tool for enforcing below rules for code table entries
• Reduced table size for scalar decoder
• Tool for generating code table entries

ldpc_scalar.vhd

scalar LDPC decoder configuration

ldpc_scalar.hh

scalar LDPC decoder configuration

ldpc_vector.vhd

vector LDPC decoder configuration

ldpc_vector.hh

vector LDPC decoder configuration

table_scalar.txt

Transformed DVB T2 B7 code table for scalar decoder:

• Rows are sorted by location offsets to maximally space out same offsets on consecutive columns.
• Columns are sorted by count to minimize pipeline stalls.

table_vector.txt

Transformed and manipulated DVB T2 B7 code table for vector length of 15:

• Rows are sorted by location offsets to keep same offsets consecutive.
• Above sorting helps maximally spacing out same offsets on consecutive columns.
• Swapped columns to avoid same offsets on consecutive columns.
• Columns are sorted by count to minimize pipeline stalls.

check_table_scalar_txt.hh

check table_scalar.txt for data hazards

The following rules must apply to the table for the decoder to work correctly:

• Order of location offsets must avoid data hazards caused by the pipeline.
• Optional: Keep same count rows consecutive to avoid pipeline stalls.

check_table_vector_txt.hh

check table_vector.txt for data hazards

The following rules must apply to the table for the decoder to work correctly:

• Rows containing DDSMs must keep locations with same offset consecutive.
• Order of location offsets must avoid data hazards caused by the pipeline.
• Optional: Keep same count rows consecutive to avoid pipeline stalls.

table_vector.vhd

code table generated from table_vector.txt by generate_table_vector_vhd.cc

cnp_scalar_tb.vhd

testbench for the scalar check node processor

cnp_vector_tb.vhd

testbench for the vector check node processor

dec_scalar_tb.vhd

testbench for the scalar decoder

dec_vector_tb.vhd

testbench for the vector decoder

dec_scalar.vhd

SISO scalar decoder for IRA-LDPC codes

dec_vector.vhd

SISO vector decoder for IRA-LDPC codes

cnp_scalar.vhd

scalar check node processor

cnp_vector.vhd

vector check node processor

buf_scalar.vhd

buffer for the scalar check node processor

generate_cnp_scalar_tb_inp_txt.cc

generate cnp_scalar_tb_inp.txt from random noise

generate_cnp_scalar_tb_exp_txt.cc

generate cnp_scalar_tb_exp.txt processed from cnp_scalar_tb_inp.txt

buf_vector.vhd

buffer for the vector check node processor

generate_cnp_vector_tb_inp_txt.cc

generate cnp_vector_tb_inp.txt from random noise

generate_cnp_vector_tb_exp_txt.cc

generate cnp_vector_tb_exp.txt processed from cnp_vector_tb_inp.txt

generate_dec_vector_tb_inp_txt.cc

Generate dec_vector_tb_inp.txt from random noise

generate_dec_vector_tb_exp_txt.cc

Generate dec_vector_tb_exp.txt decoded from dec_vector_tb_inp.txt

generate_table_vector_vhd.cc

Generate table_vector.vhd from table_vector.txt

generate_table_model_txt.cc

Generate table_model.txt from table_input.txt

This formulates a linear programming model of the code table to solve potential data hazards.

generate_table_vector_txt.cc

Generate table_vector.txt from table_input.txt and table_solution.txt

The solution table_solution.txt of the problem formulated in table_model.txt is used to permutate the lines in table_input.txt to create a data hazard free table_vector.txt.

add_scalar.vhd

scalar saturating addition

add_vector.vhd

vector saturating addition

rol_vector.vhd

rotate left vector elements

ror_vector.vhd

rotate right vector elements

bnl_scalar.vhd

scalar bit node links

bnl_vector.vhd

vector bit node links

cnt_vector.vhd

counts for the vector decoder

loc_vector.vhd

locations for the vector decoder

var_scalar.vhd

scalar variable nodes

var_vector.vhd

vector variable nodes

wdf_vector.vhd

write disable flags for the vector decoder

exclusive_reduce.hh

Reduce N times while excluding ith input element

It computes the following, but having only O(N) complexity and using O(1) extra storage:

	output[0] = input[1];
	output[1] = input[0];
	for (int i = 2; i < N; ++i)
		output[i] = op(input[0], input[1]);
	for (int i = 0; i < N; ++i)
		for (int j = 2; j < N; ++j)
			if (i != j)
				output[i] = op(output[i], input[j]);

cnp_scalar.hh

scalar check node processor reference code

The C++ code below is also included in cnp_scalar.hh:

void cnp(int *output, const int *input, int cnt, int beta)
{
	int imags[cnt];
	for (int i = 0; i < cnt; ++i)
		imags[i] = min(max(abs(input[i]) - beta, 0), 31);

	int omags[cnt];
	CODE::exclusive_reduce(imags, omags, cnt, min);

	int isgns[cnt];
	for (int i = 0; i < cnt; ++i)
		isgns[i] = sgn(input[i]);

	int osgns[cnt];
	CODE::exclusive_reduce(isgns, osgns, cnt, mul);

	for (int i = 0; i < cnt; ++i)
		output[i] = osgns[i] * omags[i];
}

cnp_vector.hh

vector check node processor reference code

dec_scalar.hh

scalar IRA-LDPC decoder reference code

dec_vector.hh

vector IRA-LDPC decoder reference code