dist_rw.c File Reference

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

Include dependency graph for dist_rw.c:

Go to the source code of this file.

Macros
#define	NEW   1

Functions
int	do_RW_dist (params_t *const p)
	distance of a classical or quantum CSS code

Macro Definition Documentation

NEW

#define NEW   1

Function Documentation

do_RW_dist()

int do_RW_dist

(

params_t *const

p

)

distance of a classical or quantum CSS code

---

The program implements two methods:

1. 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

Random Information Set search for small-E logical operators.

Parameters

dW	weight increment from the minimum found
p	pointer to global parameters structure
classical	set to 1 for classical code (do not use L matrix), 0 otherwise

Returns

minimum weight of a CW found (or -weight if early termination condition is reached), or 0 if no codewords with w<wmax have been found.

whether to verify logical ops as a vector or individually

actual vector in sparse form

1. Construct random column permutation P

identity column permutation

list of pivot columns

bitmask of pivot columns

random pivots LAPAC-style

< corresponding permutation

full row echelon form of H (gauss) using the order in perm

it is a bit faster to transpose mH first.

calculate sparse version of each vector (list of positions) p p``p # pivot columns marked with p
[1 a1 b1 ] -> [a1 1 a2 a3 0 ] [ a2 1 b2 ] [b1 0 b2 b3 1 ] [ a3 1 b3 ]

each row in the dual matrix

how many non-zero elements

weight limit of candidates of interest (the same with any debug value)

older version going over columns of H

function mzd_find_pivot() walks over columns one-by-one to find a non-zero bit. Returns 1 if a non-zero bit was found. WARNING: this is the slowest option!!!

NEW==1, use transposed H – the fastest version of the code

cw of no interest

sort the column indices

expensive: verify orthogonality

verify logical operator

no need to verify

we got non-trivial codeword!

TODO: try local search to lerr (if 2 or larger)

at this point we have cnt codeword indices in ee

early termination condition

this distance value is of little interest;

stop right away

end of the dual matrix rows loop

end of steps random window

early termination label

clean up

Definition at line 38 of file dist_rw.c.

References CW_VEC_T::arr, check_min_hits_convergence(), codeword_add_maybe(), codeword_feed_limit(), codeword_maxc_reached(), csr_t::cols, csr_free(), csr_transpose(), CW_SRC_RW_UNIFORM, CW_SRC_RW_WINDOW, DBG_CODEWORDS, DBG_LARGE, DBG_PROGRESS, DBG_STATUS, DBG_SUMMARY, ERROR, HASH_ITER, localized_window_perm(), mzd_from_csr(), mzd_nullspace(), p, perm_p_trans(), rand_uniform(), refresh_nullspace_basis(), csr_t::rows, and CW_VEC_T::weight.