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

A. 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 -weigt if early termination condition is reached). Or 0 if no codewords wit 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

list of pivot columns

list of pivot columns

random pivots LAPAC-style

< corresponding permutation

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

construct skip-pivot permutation

it is a bit faster to transpose mH first.

calculate sparse version of each vector (list of positions) p pp # 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

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 37 of file dist_rw.c.

References params_t::classical, codeword_add_maybe(), params_t::codewords, csr_t::cols, params_t::debug, params_t::dmax, params_t::dW, ERROR, params_t::maxC, params_t::min_w, mzd_from_csr(), params_t::num_cws, params_t::outC, p, perm_p_trans(), params_t::spaH, params_t::spaL, params_t::steps, params_t::wmax, and params_t::wmin.