はじめに

本記事では、通信を始めとする様々な分野で利用される誤り訂正符号の一つ、QC-LDPC符号の符号設計方法に関して説明します。具体的には、最小ハミング距離が間接的に長くなるように、検査行列内の非ゼロ成分である巡回行列を配置する探索アルゴリズムを紹介します。

関連記事

本記事の導入となる記事です。前提となる内容が含まれるため、一読いただけると理解が深まると思います。

目的

・LDPC符号の符号設計における最小ハミング距離を長くする方法の紹介
・QC-LDPC符号の符号設計への上記手法の適用とプログラムの紹介

対象読者

・LDPC符号の符号設計に関心がある方
・QC-LDPC符号の符号設計用プログラムの実装に関心がある方

注意事項

GF(2)上のLDPC符号、QC-LDPC符号を前提とします。従って、検査行列の成分は0か1で表されます。

参考文献

本文

0. 背景

誤り訂正符号においては、最小ハミング距離を長くすることが誤り訂正能力を高めることに繋がります。
代数的なテクニックを用いない場合、最小ハミング距離の探索は組み合わせ問題となります。1000ビットを超える実用的な符号語の長さ（符号長）になると、探索範囲が広すぎるため、最小ハミング距離が長い符号を設計することが困難になります。そのため、最小ハミング距離が長い符号を設計するための代替策として、LDPC符号の検査行列内の非ゼロ成分を頂点とするループが短くならないようにする手法が適用されます。

1. 最小ハミング距離とループの関係

本章では、QC-LDPC符号の例を説明する前段階として、サイズの小さいLDPC符号の例を用いて、最小ハミングとループの関係を説明します。

1.1 最小ハミング距離の見積もり

先ず、最小ハミング距離2の符号を考えます。説明のために、下記の4x4の疑似的な検査行列(H)を考えます。

1 1 1 0
1 0 1 1
0 1 0 1

最小ハミング距離はXORしてゼロベクトルになる検査行列の列ベクトルの組み合わせを見つけることで分かります。
この検査行列の例では、赤字で示した第一列ベクトルと第三列ベクトルをXORするとゼロベクトルになり、最小ハミング距離は2と分かります。
XORしてゼロベクトルになる検査行列の列ベクトルの組み合わせは、符号語に対する特定のビット反転が生じた場合に検査行列で検知できないビット反転のパターンに相当します。この例では、4ビットの符号語(c)に対して、第一ビット目と第三ビット目が誤り(n)によりビット反転しても、検査行列で検知できない（訂正できない）ことを意味します。尚、数式で表すと、以下となります。

Hc = 0

Hn = 0  \\ n = [1,0,1,0]

H(c+n) = Hc + Hn = 0

次に、最小ハミング距離3の符号を考えます。説明のために、下記の4x4の疑似的な検査行列(H)を考えます。
この検査行列の場合は、どの2つの列ベクトルのペアでXORをしてもゼロベクトルにならないため、最小ハミング距離は2より大きいと言えます。検査行列の第二列ベクトルと第三列ベクトルとの第四列ベクトルをXORすると、ゼロベクトルになることから、最小ハミング距離は3と分かります。

1 0 1 1
1 0 0 0
0 1 0 1
0 1 1 0

ここまでで、検査行列の列ベクトルをXORすることで、最小ハミング距離が見積もれると分かったと思います。
上記の例では、検査行列のサイズ（符号語の長さ）が小さいために最小ハミング距離の探索が可能でしたが、検査行列のサイズ（符号長）が長くなると探索に時間を要することになり、見積もりは困難になります。従って、最小ハミング距離への寄与が大きいと考えられる検査行列の非ゼロ成分を頂点とするループに着目した符号設計がなされます。

1.2 検査行列の非ゼロ成分を頂点とするループ

列ベクトル同士のXORによって、最小ハミング距離を見積もれることを説明してきました。XORの演算であるため、これは列ベクトル内の1に着目すれば良いと言えます。先ほどと同じ最小ハミング距離が3の検査行列に対して、対応する1を赤字で示したものを以下に示します。

1 0 1 1
1 0 0 0
0 1 0 1
0 1 1 0

よくよく見ると、赤字の1を頂点とする8の字のループが見えると思います。（今回は8の字ですが、8の字である必要はなく、閉じたループができることが重要です。）このように、列ベクトルのXORで消える1は、何らかのループを形成します。最小ハミング距離となる列ベクトルの集合が仮に分かった場合、その列ベクトルの集合には1つ以上のループが含まれることになります。
従って、1を頂点とするループとして短いものができないようにすると、それらループの組み合わせの結果として決まる最小ハミング距離は長くなると考えられます。尚、このループの長さは辺の数または頂点の数で数え上げるため、6となります。

上記の検査行列のように、列方向の非ゼロ成分（1）の数が2場合は、最も短いループの長さの半分が最小ハミング距離に対応します。一方で、列方向の非ゼロ成分（1）の数が2より大きい場合は、最も短いループの長さの半分に対して、最小ハミング距離は等しいか、より長くなります。例として、先ほどの検査行列の下に2行を追加したものを示します。

1 0 1 1
1 0 0 0
0 1 0 1
0 1 1 0
0 0 1 1
1 1 0 0

この検査行列においては、列方向の非ゼロ成分（1）の数が2から3に増えており、第二列ベクトルと第三列ベクトルとの第四列ベクトルをXORしてもゼロベクトルとならなくなったため、ループの長さよりもハミング距離が長くなることが分かります。このように、列方向の非ゼロ成分の数が3以上になると、ループの長さの半分が最小ハミング距離になるとは限りませんが、短いループの存在をなくすことが最小ハミング距離を長くすることに繋がると予想できます。従って、短いループが存在しないように非ゼロ成分を配置することを目的とした、LDPC符号の符号設計が行われます。

2. QC-LDPC符号における符号設計方法

本章では、QC-LDPC符号におけるループの検知方法と符号設計のプログラムを紹介します。

2.1 非ゼロ成分である巡回行列を頂点としたループ

QC-LDPC符号の場合も、非ゼロ成分を頂点をするループに着目します。QC-LDPC符号の非ゼロ成分の配置は、巡回行列の配置と巡回行列のシフト数で表されます。
先ずは、巡回行列におけるループの例を説明します。
下記のように、4x4の巡回行列を2行ブロック、2列ブロック配置した検査行列を考えます。

これを巡回シフト数で表すと、以下となります。

この例では、意図的にループができるように配置しているため、4つの巡回行列それぞれの1を頂点としたループが4つ確認できると思います。参考として、ループの一つを赤矢印で示した図を以下に示します。

このようなループを巡回シフト数に着目して確認する際には、以下のように巡回シフト数の和が0となるかで判断します。

0 + 3 + 0 + 1 = 4 = 0  \quad (mod \quad 4 )

これらのことから、QC-LDPC符号におけるループの検知は以下の2ステップとなります。

巡回行列を頂点とするループを探す。
検知したループの巡回シフト数を足し合わせた際に0となれば、ループありと判断する。

1では、巡回行列自体が非ゼロを含むものなので、先ずは大まかにループの候補を見つけるという意味で、巡回行列を頂点とするループを探します。
2では、巡回シフト数を含めて考えたときに、ループが形成されているかを考えます。巡回行列サイズをN、第i番目の巡回行列の巡回シフト数を$a_i$としたときに以下の式が成り立つときに、長さLのループが形成されていると判断します。

\sum_{i=0}^{L-1}a_i = 0 \quad(mod \quad N)

3. QC-LDPC符号の符号設計用プログラム

3.1 プログラムの概要

QC-LDPC符号の符号設計を行うためのプログラムを作成しました。
プログラムの動きとしては、ある長さ以下のループを含まないように、巡回行列の配置と巡回シフト数を列ブロック単位で乱数探索しながら検査行列を作り上げるものです。ソースコードは冗長であるため、末尾の付録に示してあります。

3.2 プログラムの実行

プログラムの実行に関して説明します。
引数は以下の6つです。

#1 : Size of Circular Matrix
#2 : Number of Column Blocks
#3 : Number of Row Blocks
#4 : Number of Column Weights
#5 : Threshold of Loop Length
#6 : Seed Number

#4は列ブロック当たりに配置する巡回行列の数です。
一方で、行ブロック当たりに配置する巡回行列の数は、プログラム内で、可能な限り均一になるようにしています。
#5は検査行列に含まないようにするループの長さを指定します。今回は設定の上限を8としています。
#6は乱数のシードで、検査行列の生成に失敗した場合に変更して再度実行します。

プログラムの実行例（python3 main.py 32 16 4 3 8 2222）を以下に示します。

python3 main.py 32 16 4 3 8 2222

This program is to search generation matrix QC_LDPC codes with minimum Hamming distance more than X.
# 0
# 1
# 2
find 4 loop at columns : 0 1 : ( 32 + 32 ) %  32  = 0
# 3
# 4
# 5
# 6
# 7
# 8
# 9
find 4 loop at columns : 0 3 : ( 13 + 19 ) %  32  = 0
# 10
find 4 loop at columns : 0 1 : ( 26 + 38 ) %  32  = 0
# 11
# 12
find 4 loop at columns : 1 2 : ( 31 + 33 ) %  32  = 0
# 13
find 4 loop at columns : 1 3 : ( 41 + 23 ) %  32  = 0
# 14
find 4 loop at columns : 1 3 : ( 47 + 17 ) %  32  = 0
# 15
find 4 loop at columns : 2 3 : ( 47 + 17 ) %  32  = 0
#1 : Size of Circular Matrix: 32
#2 : Number of Columns: 16
#3 : Number of Rows: 4
#4 : Column Weights: 3
#5 : Max ROW Weights: 12
#6 : Hamming Distance is more than  8
#7 : Seed Number: 2222
Code Length [bit] :  512
Code RATE :  0.75
in the following matrix, -1 shows zero matrix and the other number is circular shift in circular matrix.
Suceeded!
[[ 1 17 31 -1  5 -1 16  5 -1 12 25 22  3  4 -1  7]
 [16 -1 16 16 -1 16 15 21 26 -1 22 23 15 25 31 -1]
 [-1 20 22 24 17 20  1 -1  5 21  8 -1 13 -1 14 23]
 [ 8 26 -1  9  4 12 -1  7 30 11 -1  5 -1 14  9  8]]
Row Weights: [12, 12, 12, 12]
Col Weights: [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]

出力の前半は乱数探索の途中経過を表示しています。
出力の中盤は引数で渡したパラメータや符号長と符号化率のパラメータを表示しています。
出力の後半は探索の成否や、生成した検査行列の巡回シフト数の分布、列及び行ブロック単位の非ゼロ成分である巡回行列の数を表示しています。尚、巡回シフト数における-1はゼロ行列を意味します。今回は、列及び行ブロック単位の非ゼロ成分の数が、3と12で均一になっていると確認できます。

Suceeded!
[[ 1 17 31 -1  5 -1 16  5 -1 12 25 22  3  4 -1  7]
 [16 -1 16 16 -1 16 15 21 26 -1 22 23 15 25 31 -1]
 [-1 20 22 24 17 20  1 -1  5 21  8 -1 13 -1 14 23]
 [ 8 26 -1  9  4 12 -1  7 30 11 -1  5 -1 14  9  8]]
Row Weights: [12, 12, 12, 12]
Col Weights: [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]

4. まとめ

本記事では、QC-LDPC符号の符号設計方法に関して説明しました。符号長1000ビットを超えるような実用的な長さの符号を設計する際には、最小ハミング距離を組み合わせ問題的に探索することは困難であるため、非ゼロ成分を頂点とするループの探索と非ゼロ成分の再配置が行われます。QC-LDPC符号において、短いループが形成されないように、検査行列内の非ゼロ成分である巡回行列の配置を乱数探索するアルゴリズムを紹介しました。

付録（Pythonで実装したプログラム）

QC-LDPC符号において、巡回行列の配置を乱数探索するアルゴリズムを実装したプログラムを示します。

main.py

import numpy as np
import random
import sys
import math
from check_loop import check_qc_loop

FLAG_DEBUG = 0 
MAX_TRIALS = 10000

# set -1 to a specific column of the matrix
def refresh_col(mat,col,num):
	for i in range(num):
		mat[col][i] = -1
# initialize matrix
def init_mat(mat,num_c,num_r):
	for i in range(num_c):
		refresh_col(mat,i,num_r)

# set circular matrix in a specific column of the matrix
def set_qc_num_to_col(mat,num_weight,search_col,candi_row,candi_qc):
	for i in range(num_weight):
		mat[search_col][candi_row[i]] = candi_qc[i]

# count row and column weights of the matrix
def count_weights(NUM_ROW,NUM_COL,mat):
	rc = []
	cc = []
	for i in range(NUM_ROW):
		count = 0
		for j in range(NUM_COL):
			if mat[i][j] != -1:
				count += 1
		rc.append(count)
	for j in range(NUM_COL):
		count = 0
		for i in range(NUM_ROW):
			if mat[i][j] != -1:
				count += 1
		cc.append(count)
	return rc, cc		
	
def main(args):
	QC_SIZE			= int(args[1])
	NUM_COL			= int(args[2])
	NUM_ROW			= int(args[3])
	NUM_COL_WEIGHT	= int(args[4])
	THRESHOLD		= int(args[5])
	SEED			= int(args[6])
	random.seed(SEED)
	MAX_ROW_WEIGHT	= math.ceil(NUM_COL_WEIGHT*NUM_COL/NUM_ROW)

	# initialization of QC_LDPC
	mat_qc_ldpc = np.zeros((NUM_COL,NUM_ROW),dtype=int)
	counter_row_weight = np.zeros(NUM_ROW,dtype=int)
	init_mat(mat_qc_ldpc,NUM_COL,NUM_ROW)

	ERR_FLAG = 0
	search_col = 0
	val = [k for k in range(NUM_ROW)]
	
	# greedy search to create the parity check matrix of QC-LDPC
	for i in range(NUM_COL):
		print("#",i)
		trial = 0
		ERR_FLAG = 1
		
		while(trial < MAX_TRIALS):
			# pick up the number of columns to put circular matrix 
			tmp_val =[val[i] for i in range(len(val))]
			if len(val)<NUM_COL_WEIGHT:
				LEN=len(val)
				FLAG_FRESH = 1
			else:
				LEN=NUM_COL_WEIGHT
				FLAG_FRESH = 0
			rand_list = random.sample(range(len(val)),LEN)
			rand_list = np.sort(rand_list)[::-1]
			candi_row = []
			if FLAG_DEBUG==1:
				print(LEN,val,rand_list)
			for k in range(LEN):
				candi_row.append(val.pop(rand_list[k]))
			
			if FLAG_FRESH == 1:
				while(1):
					val = [k for k in range(NUM_ROW)]
					LEN1 = NUM_COL_WEIGHT - LEN
					rand_list1 = random.sample(range(len(val)),LEN1)
					rand_list1 = np.sort(rand_list1)[::-1]
					if FLAG_DEBUG==1:
						print(LEN1,val,rand_list)
					candi_row1 = []
					for k in range(LEN1):
						candi_row1.append(val.pop(rand_list1[k]))
					tmp_candi = candi_row + candi_row1
					if( len(tmp_candi) == len(set(tmp_candi)) ):
						candi_row = tmp_candi
						break
			# set the number of cyclic shift 
			candi_qc  = random.sample(range(0,QC_SIZE),k=NUM_COL_WEIGHT)
			if(check_qc_loop(mat_qc_ldpc,i,candi_row,candi_qc,NUM_COL,NUM_ROW,NUM_COL_WEIGHT,QC_SIZE,THRESHOLD)):
				set_qc_num_to_col(mat_qc_ldpc,NUM_COL_WEIGHT,search_col,candi_row,candi_qc)
				search_col += 1
				ERR_FLAG = 0
				break
			trial += 1
			val = tmp_val

		if ERR_FLAG == 1:
			break
	
	print("#1 : Size of Circular Matrix:",QC_SIZE)
	print("#2 : Number of Columns:",NUM_COL)
	print("#3 : Number of Rows:",NUM_ROW)
	print("#4 : Column Weights:",NUM_COL_WEIGHT)
	print("#5 : Max ROW Weights:",MAX_ROW_WEIGHT)
	print("#6 : Hamming Distance is more than ", THRESHOLD)
	print("#7 : Seed Number:",SEED)
	print("Code Length [bit] : ",QC_SIZE * NUM_COL)
	print("Code RATE : ", (NUM_COL-NUM_ROW)/NUM_COL)
	print("in the following matrix, -1 shows zero matrix and the other number is circular shift in circular matrix.") 
	
	if ERR_FLAG == 1:
		set_qc_num_to_col(mat_qc_ldpc,NUM_COL_WEIGHT,search_col,candi_row,candi_qc)
		print("ERROR")
		print(mat_qc_ldpc.T)
	else:	
		print("Suceeded!")
		print(mat_qc_ldpc.T)
	row_weight_counter, col_weight_counter = count_weights(NUM_ROW,NUM_COL,mat_qc_ldpc.T)
	print("Row Weights:",row_weight_counter)
	print("Col Weights:",col_weight_counter)
	filename = 'qc_ldpc_('+str(QC_SIZE)+')_('+str(NUM_COL)+'_'+str(NUM_ROW)+')_W='+str(NUM_COL_WEIGHT)+'_T='+str(THRESHOLD)
	np.savetxt(filename+'.txt',mat_qc_ldpc.T,fmt='%d,')

if __name__ == '__main__':
	print("This program is to search generation matrix QC_LDPC codes with minimum Hamming distance more than X.")
	args = sys.argv
	if len(args) == 7:
		if args[1].isdigit() & args[2].isdigit() & args[3].isdigit() & args[4].isdigit() & args[5].isdigit() & args[6].isdigit():
			main(args)
	else:
		print("Set 6 Arguments as int")
		print("#1 : Size of Circular Matrix")
		print("#2 : Number of Columns")
		print("#3 : Number of Rows")
		print("#4 : Number of Column Weights")
		print("#5 : Threshold of Minimum Hamming Distance(4 or 6)")
		print("#6 : Seed Number")
		print("example: python3 main.py 32 16 4 3 8 2222")

check_loop.py

import numpy as np

FLAG_DEBUG = 1
MAX_TRIALS = 10000


def check_qc_loop(mat,search_col,candi_row,candi_qc,num_c,num_r,num_weight,qc_size,threshold):
	ERROR = 0
	if threshold == 4:
		ERROR = check_qc_4loop(mat,search_col,candi_row,candi_qc,num_c,num_r,num_weight,qc_size)
	elif threshold == 6:
		ERROR = check_qc_4loop(mat,search_col,candi_row,candi_qc,num_c,num_r,num_weight,qc_size)
		if ERROR == 0:
			ERROR = check_qc_6loop(mat,search_col,candi_row,candi_qc,num_c,num_r,num_weight,qc_size)
	elif threshold == 8:
		ERROR = check_qc_4loop(mat,search_col,candi_row,candi_qc,num_c,num_r,num_weight,qc_size)
		if ERROR == 0:
			ERROR = check_qc_6loop(mat,search_col,candi_row,candi_qc,num_c,num_r,num_weight,qc_size)
			if ERROR == 0:
				ERROR = check_qc_8loop(mat,search_col,candi_row,candi_qc,num_c,num_r,num_weight,qc_size)
	else:
		ERROR = 1
		print("set threshold 4,6,or 8")
	return ERROR

def check_qc_4loop(mat,search_col,candi_row,candi_qc,num_c,num_r,num_weight,qc_size):
	
	base = np.zeros(num_r)
	accu = np.zeros(num_r)
	
	for i in range(num_weight):
		base[candi_row[i]] += candi_qc[i]
		accu[candi_row[i]] += 1
	
	tmp_base = np.zeros(num_r,dtype=int)
	tmp_accu = np.zeros(num_r,dtype=int)
	
	FLAG_END = 0

	for k in range(search_col):
		for i in range(num_weight):
			tmp_base[candi_row[i]] = candi_qc[i]
			tmp_accu[candi_row[i]] = 1
		for j in range(num_r):
			if mat[k][j] != -1:
				tmp_base[j] += mat[k][j] 
				tmp_accu[j] += 1
		FLAG_END = 0
		for l0 in range(0,num_r-1):
			if tmp_accu[l0] == 2:
				for l1 in range(l0+1,num_r):
					num_loop = tmp_accu[l0] + tmp_accu[l1]
					if tmp_accu[l1] == 2:
						val = (tmp_base[l0] + tmp_base[l1]) % qc_size 
						if val == 0:
							FLAG_END = 1
							if FLAG_DEBUG == 1:
								print("find 4 loop at columns :", l0,l1,": (",tmp_base[l0],"+",tmp_base[l1],") % ",qc_size," =",val)
							break
			if FLAG_END == 1:
				break
		if FLAG_END == 1:
			break
	return (FLAG_END+1)%2

def check_qc_6loop(mat,search_col,candi_row,candi_qc,num_c,num_r,num_weight,qc_size):
	
	base = np.zeros(num_r)
	accu = np.zeros(num_r)
	
	for i in range(num_weight):
		base[candi_row[i]] += candi_qc[i]
		accu[candi_row[i]] += 1
	
	tmp_base = np.zeros(num_r,dtype=int)
	tmp_accu = np.zeros(num_r,dtype=int)
	
	FLAG_END = 0

	for k in range(0,search_col-1):
		for k0 in range(k+1,search_col):
			for i in range(num_weight):
				tmp_base[candi_row[i]] = candi_qc[i]
				tmp_accu[candi_row[i]] = 1
			for j in range(num_r):
				if mat[k][j] != -1:
					tmp_base[j] += mat[k][j] 
					tmp_accu[j] += 1
				if mat[k0][j] != -1:
					tmp_base[j] += mat[k0][j] 
					tmp_accu[j] += 1
			FLAG_END = 0
			for l0 in range(0,num_r-2):
				if tmp_accu[l0] == 2:
					for l1 in range(l0+1,num_r-1):
						if tmp_accu[l1] == 2:
							for l2 in range(l1+1,num_r):
								if tmp_accu[l2] == 2:
									val = (tmp_base[l0] + tmp_base[l1] + tmp_base[l2]) % qc_size 
									if val == 0:
										FLAG_END = 1
										if FLAG_DEBUG == 1:
										print("find 6 loop at columns :", l0,l1,l2,": (",tmp_base[l0],"+",tmp_base[l1],"+",tmp_base[l2],") % ",qc_size," =",val)
										break
						if FLAG_END == 1:
							break
				if FLAG_END == 1:
					break
			if FLAG_END == 1:
				break
		if FLAG_END == 1:
			break
	return (FLAG_END+1)%2

def check_qc_8loop(mat,search_col,candi_row,candi_qc,num_c,num_r,num_weight,qc_size):
	
	base = np.zeros(num_r)
	accu = np.zeros(num_r)
	
	for i in range(num_weight):
		base[candi_row[i]] += candi_qc[i]
		accu[candi_row[i]] += 1
	
	tmp_base = np.zeros(num_r,dtype=int)
	tmp_accu = np.zeros(num_r,dtype=int)
	
	FLAG_END = 0

	for k in range(0,search_col-2):
		for k0 in range(k+1,search_col-1):
			for k1 in range(k0+1,search_col):
				for i in range(num_weight):
					tmp_base[candi_row[i]] = candi_qc[i]
					tmp_accu[candi_row[i]] = 1
				for j in range(num_r):
					if mat[k][j] != -1:
						tmp_base[j] += mat[k][j] 
						tmp_accu[j] += 1
					if mat[k0][j] != -1:
						tmp_base[j] += mat[k0][j] 
						tmp_accu[j] += 1
					if mat[k1][j] != -1:
						tmp_base[j] += mat[k1][j] 
						tmp_accu[j] += 1
				
				FLAG_END = 0
				## loop with 4 rows
				for l0 in range(0,num_r-3):
					if tmp_accu[l0] == 2:
						for l1 in range(l0+1,num_r-2):
							if tmp_accu[l1] == 2:
								for l2 in range(l1+1,num_r-1):
									if tmp_accu[l2] == 2:
										for l3 in range(l2+1,num_r):
										if tmp_accu[l2] == 2:
										val = (tmp_base[l0] + tmp_base[l1] + tmp_base[l2] + tmp_base[l3]) % qc_size 
										if val == 0:
										FLAG_END = 1
										if FLAG_DEBUG == 1:
										print("find 8 loop at columns :", l0,l1,l2,l3,": (",tmp_base[l0],"+",tmp_base[l1],"+",tmp_base[l2],"+",tmp_base[l3],") % ",qc_size," =",val)
										break
									if FLAG_END == 1:
										break
							if FLAG_END == 1:
								break
					if FLAG_END == 1:
						break
				## loop with 4 rows
				for l0 in range(0,num_r-2):
					if tmp_accu[l0] % 2 == 0:
						for l1 in range(l0+1,num_r-1):
							if tmp_accu[l1] % 2 == 0:
								for l2 in range(l1+1,num_r):
									if tmp_accu[l2] % 2 == 0:
										if (tmp_accu[l0] + tmp_accu[l1] + tmp_accu[l2]) == 8:
										val = (tmp_base[l0] + tmp_base[l1] + tmp_base[l2]) % qc_size 
										if val == 0:
										FLAG_END = 1
										if FLAG_DEBUG == 1:
										print("find 8 loop at columns :", l0,l1,l2,": (",tmp_base[l0],"+",tmp_base[l1],"+",tmp_base[l2],") % ",qc_size," =",val)
										break
									if FLAG_END == 1:
										break
							if FLAG_END == 1:
								break
					if FLAG_END == 1:
						break
				## loop with 2 rows
				if (qc_size % 2) == 0:
					for l0 in range(0,num_r-2):
						if tmp_accu[l0] % 2 == 0:
							for l1 in range(l0+1,num_r-1):
								if tmp_accu[l1] % 2 == 0:
									if (tmp_accu[l0] + tmp_accu[l1]) == 8:
										val = (tmp_base[l0] + tmp_base[l1]) % int(qc_size/2) 
										if val == 0:
										FLAG_END = 1
										if FLAG_DEBUG == 1:
										print("find twice 4 loop at columns :", l0,l1,": (",tmp_base[l0],"+",tmp_base[l1],") % ",qc_size," =",val)
										break
								if FLAG_END == 1:
									break
						if FLAG_END == 1:
							break
				if FLAG_END == 1:
					break
			if FLAG_END == 1:
				break
		if FLAG_END == 1:
			break
	return (FLAG_END+1)%2