[編碼理論] LDPC decode (C++)

 編碼理論的期末作業其中一題是

Continued from the very end of our handout’s Page CT.087.1, perform one more iteration of BP (including one upward (i.e. variable-to-check) BP and one downward (i.e. check-to-variable) BP). Then compute the soft decision (i.e. Prob(bit=1)) for all of the eight variable bits.

原本打算拿起計算機開始算，但算完第一個機率後，決定還是寫個程式來把答案直接印出來，所以底下的程式真的是亂寫+不知道有沒有符合理論，也沒特別抓蟲了

我們先來看LDPC的解碼流程: 

Check Node Update :

求出藍色箭頭的值(v->c)，第一次是使用bit本身的機率，最後會在介紹有其他機率之後怎麼求

Bit Node Update :

由剛剛藍色箭頭(這邊變紅色了) 來求出紫色箭頭的值(每個CheckNode -> Variable Node 的機率，底下是 C1-->V2的示意圖)

其中 

Termination:

剛剛上張圖中的P2 計算後會得到0.3188, 當然依序就可以求出其他值(所有的紫色箭頭)，結果會如下圖所示，其中v2最後我們要計算的soft decode value是 0.3188 * 0.4057 * 0.6308 (這邊*是指p * q / ((p * q) + ((1 - p) * (1 - q))) ) 

syndrome 的值是將decode 的值做+運算，當syndrome 都是0的時候就不需要再iteration

那這邊的syndrome 是0101，就必須繼續做iteration

要做第二次的iteration就可以來update check node，做法如下

將所有藍色箭頭更新完就能得到下圖，就是我們的check node update

那如果透過執行程式 我們能很快知道 iteration2的結果，這份作業是要我們完成iteration 3，原本算完一個值我就亂了，只好寫個簡單的程式碼 😂

>>>>>>>>>>>>>>iteration 2

[Check node update]

v2 -> c1: 0.5385

v4 -> c1: 0.7592

v5 -> c1: 0.8241

v8 -> c1: 0.109

v1 -> c2: 0.4301

v2 -> c2: 0.4443

v3 -> c2: 0.6683

v6 -> c2: 0.9173

v3 -> c3: 0.7918

v6 -> c3: 0.9447

v7 -> c3: 0.6835

v8 -> c3: 0.07988

v1 -> c4: 0.4044

v4 -> c4: 0.7409

v5 -> c4: 0.8118

v7 -> c4: 0.4902

[Bit Node update]

c1 -> v2: 0.3686

c1 -> v4: 0.4805

c1 -> v5: 0.4844

c1 -> v8: 0.5129

c2 -> v1: 0.4843

c2 -> v2: 0.4804

c2 -> v3: 0.5065

c2 -> v6: 0.5026

c3 -> v3: 0.3628

c3 -> v6: 0.41

c3 -> v7: 0.2819

c3 -> v8: 0.5953

c4 -> v1: 0.4971

c4 -> v4: 0.5012

c4 -> v5: 0.5009

c4 -> v7: 0.4713

[Termination]

v1: 0.3183

v2: 0.4797

v3: 0.7221

v4: 0.7856

v5: 0.8423

v6: 0.9305

v7: 0.4993

v8: 0.0975

[Code]

其中帶入參數有

	#include <iostream>
	#include <vector>
	#include <iomanip>
	using namespace std;
	double butterfly(double p, double q)
	{
	return (p * (1 - q)) + ((1 - p) * q);
	}
	double star(double p, double q)
	{
	return p * q / ((p * q) + ((1 - p) * (1 - q)));
	}
	int main()
	{
	vector<vector<int>> CheckNode{{2, 4, 5, 8}, {1, 2, 3, 6}, {3, 6, 7, 8}, {1, 4, 5, 7}};
	double CheckNodeU[4][9] = {0};
	double BitNodeU[4][9] = {0};
	double var;
	double VarNode[] = {0,
	0.3346,
	0.6308,
	0.8164,
	0.7977,
	0.8500,
	0.9502,
	0.7403,
	0.0652};
	for (int iteration = 1; iteration <= 3; iteration++)
	{
	cout << ">>>>>>>>>>>>>>iteration " << iteration << endl;
	cout << "[Check Node Update]" << endl;
	for (int i = 0; i < 4; i++)
	{
	for (int j = 0; j < CheckNode[i].size(); j++)
	{
	var = VarNode[CheckNode[i][j]];
	for (int k = 0; k < 4; k++)
	{
	if ((BitNodeU[k][CheckNode[i][j]] == 0) || (i == k))
	continue;
	var = star(var, BitNodeU[k][CheckNode[i][j]]);
	}
	CheckNodeU[i][CheckNode[i][j]] = var;
	cout << "v" << CheckNode[i][j] << " -> "
	<< "c" << i + 1 << ": " << setprecision(4) << var << endl;
	}
	}
	cout << "[Bit Node Update]" << endl;
	for (int i = 0; i < 4; i++)
	{
	for (int j = 0; j < CheckNode[i].size(); j++)
	{
	var = 0;
	for (int k = 0; k < CheckNode[i].size(); k++)
	{
	if (j == k)
	continue;
	var = butterfly(var, CheckNodeU[i][CheckNode[i][k]]);
	}
	BitNodeU[i][CheckNode[i][j]] = var;
	cout << "c" << i + 1 << " -> v" << CheckNode[i][j] << ": " << setprecision(4) << var << endl;
	}
	}
	cout << "[Results]" << endl;
	for (int i = 1; i < 9; i++)
	{
	var = VarNode[i];
	for (int j = 0; j < 4; j++)
	{
	if (BitNodeU[j][i] == 0)
	continue;
	var = star(var, BitNodeU[j][i]);
	}
	cout << "v" << i << ": " << var << endl;
	}
	}
	}

view raw LDPC.cpp hosted with ❤ by GitHub