#include <inttypes.h>
#include <strings.h>
#include <stdlib.h>
#include <time.h>
#include <m4ri/m4ri.h>
#include "mmio.h"
#include "uthash.h"
#include "util_hash.h"
#include "util_m4ri.h"
#include "util_io.h"
#include "dist_cc.h"

Include dependency graph for dist_cc.c:

Functions
void	one_vec_print (const one_vec_t *const pvec)
	distance of a classical or quantum CSS code
int	start_CC_recurs (one_vec_t err, one_vec_t urr, one_vec_t const syn[], const int w_limit, const int max_col_wt, const csr_t const mH, const csr_t const mHT, params_t const p)
	recursively construct codewords
int	do_CC_dist (params_t *const p)

Variables
two_vec_t *	errors =NULL

Function Documentation

◆ do_CC_dist()

int do_CC_dist ( params_t *const p )

rewrite of the cluster method function using only sparse matrices try recursive version first p_swei[]: min syndrome weight distribution to return (confinement).

lower bound certified by CC rounds only if all weights below w_start are known to be absent (not with noscan=1, unless the supplied dmin equals wmax)

expert start list: unlimited clusters from the listed columns

prepare the 1st error vector and the syndrome

go up

verify the vector

classical code

update p_swei if not in hash yet

codeword weight found

not found a codeword up to wmax

noscan=1: lower weights not scanned, only the supplied dmin (may be 0)

prescribed way to clean the hashing table

Definition at line 173 of file dist_cc.c.

References codeword_add_maybe(), codeword_maxc_reached(), csr_t::cols, csr_dump(), csr_free(), csr_max_row_wght(), csr_transpose(), CW_SRC_OTHER, DBG_CODEWORDS, DBG_LARGE, DBG_PROGRESS, DBG_SUMMARY, ERROR, errors, HASH_DEL, HASH_ITER, p, csr_t::rows, start_CC_recurs(), ONE_VEC_T::vec, and ONE_VEC_T::wei.

◆ one_vec_print()

void one_vec_print ( const one_vec_t *const pvec )

distance of a classical or quantum CSS code

Print a one_vec_t structure (indices and weight) to stdout.

The program implements two methods:

Random information set (random window) algorithm (upper bound).
This works with any code (LDPC or not). (2) depth-first codeword enumeration (connected cluster) algorithm (Lower bound or actual distance if a codeword is found.)

I. Dumer, A. A. Kovalev, and L. P. Pryadko "Distance verification..." in IEEE Trans. Inf. Th., vol. 63, p. 4675 (2017). doi: 10.1109/TIT.2017.2690381

author: Leonid Pryadko leoni.nosp@m.d.pr.nosp@m.yadko.nosp@m.@ucr.nosp@m..edu, Weilei Zeng

print entire one_vec_t structure by pointer

Definition at line 32 of file dist_cc.c.

References ONE_VEC_T::vec, and ONE_VEC_T::wei.

Referenced by start_CC_recurs().

◆ start_CC_recurs()

int start_CC_recurs	(	one_vec_t *	err,
		one_vec_t *	urr,
		one_vec_t *const	syn[],
		const int	w_limit,
		const int	max_col_wt,
		const csr_t *const	mH,
		const csr_t *const	mHT,
		params_t *const	p )

recursively construct codewords

Parameters

err	error vector with sorted components
urr	unsorted vector so far
syn	array of syndrome vectors with sorted components (indexed by weight of error)
wmax	max recursion level (max weight of an error to process)
max_col_wt	maximum column weight (used to predict early termination)
mH	matrix H (check matrix of the code or Hx for a CSS code)
mHT	matrix H transposed
mL	matrix L=Lx for a CSS code, or NULL for a classical binary code, used to check whether zero-syndrome error is trivial or not
p_swei	minimum syndrome weight array
debug	bitmap

row with the first non-zero syndrome bit

all valid positions should be to the right of here, except with the expert start list (unlimited clusters, unless start_scan=1; columns already in err are skipped below)

not there

classical code

update p_swei if not in hash yet

nothing found

Definition at line 55 of file dist_cc.c.

References codeword_add_maybe(), codeword_maxc_reached(), CW_SRC_OTHER, DBG_LEGACY, errors, csr_t::i, one_vec_print(), csr_t::p, p, start_CC_recurs(), ONE_VEC_T::vec, and ONE_VEC_T::wei.