📄 mod2sparse.html
字号:
<HTML><HEAD><TITLE> Sparse Modulo-2 Matrix Routines </TITLE></HEAD><BODY><H1> Sparse Modulo-2 Matrix Routines </H1><P>This module implements operations on matrices in which the elementsare all 0 or 1, with addition and multiplication being done modulo 2.The matrices are represented by doubly-linked lists of entriesrepresenting the elements in each row and column that are 1s, withother elements being assumed to be zero. <P>This is an appropriate representation when the matrices are sparse(ie, 0s are much more frequent that 1s). Matrices in which 0s and 1sare about equally likely may be better handled with the <AHREF="mod2dense.html">dense modulo-2 matrix routines</A>. Matricescan be converted between these two formats using the <AHREF="mod2convert.html">module-2 matrix conversion routines</A>.<P>All procedures in this module display an error message on standard error and terminate the program if passed an invalid argument (indicativeof a programming error), or if memory cannot be allocated. Errors from invalid contents of a file result in an error code being returned to the caller, with no message being printed by this module. <A NAME="rep"><H2>Representation of sparse matrices</H2></A><P>This module represents a non-zero element of a matrix (which must havethe value 1, since these are modulo-2 matrices) by a node of type<TT>mod2entry</TT>, which contains the row and column of the element,pointers to the next non-zero elements above and below in its columnand to the left and the right in its row, and two double-precisionfloating-point numbers called <B>pr</B> and <B>lr</B>, which areof no significance to this module, but which are used by the routinesfor <A HREF="decoding.html#prprp">decoding LDPC codes by probabilitypropagation</A>.<P>The <TT>mod2sparse</TT> type represents a matrix. It records thenumber of rows and columns in the matrix, and contains arrays ofpointers to the <TT>mod2entry</TT> structures for the first non-zeroelement in each row and the first non-zero element in each column.<P>Matrices must be created by the <AHREF="#allocate"><TT>mod2sparse_allocate</TT></A> procedure, whichreturns a pointer to a <TT>mod2sparse</TT> structure. When a matrixis no longer needed, the space it occupies can be freed with <AHREF="#free"><TT>mod2sparse_free</TT></A>. Elements within a matrix,represented by <TT>mod2entry</TT> nodes, are allocated as needed, andif deleted, they will be reused for new elements within the samematrix. The space they occupy is not reusable for other matrices orother purposes until the entire matrix is either freed, with <AHREF="#free"><TT>mod2sparse_free</TT></A>, or cleared to all zeros,with <A HREF="#clear"><TT>mod2sparse_clear</TT></A>, or used asthe result matrix for copying or arithmetic operations.<P><B>Header files required</B>:<TT>mod2sparse.h</TT><A NAME="dimension-sec"><P><HR><CENTER><BIG>Dimension Macros</BIG></CENTER></A><HR>The following macros take a pointer to a mod2sparse structure as theirargument, and return the number of rows or the number of columns inthe matrix pointed to, which will have been fixed when the matrix wascreated with <A HREF="#allocate">mod2sparse_allocate</A>:<BLOCKQUOTE><PRE>mod2sparse_rows(m) /* Returns the number of rows in m */mod2sparse_cols(m) /* Returns the number of columns in m */</PRE></BLOCKQUOTE><A NAME="traversal-sec"><P><HR><CENTER><BIG>Traversal Macros</BIG></CENTER></A><HR>The following macros are used to move around a sparse matrix byfollowing the pointers from one non-zero element to the next orprevious non-zero element in the same row or column. If such amovement takes one beyond the last or before first entry in a row orcolumn, or if one tries to find the first or last non-zero entry in arow or column that has no non-zero entries, the entry returned will bea special one that can be identified using the<TT>mod2sparse_at_end</TT> macro. If one is already at this specialentry, moving further wraps one around to the first or last entry.<P>The macros for finding the first or last entry in a row or columntake as their arguments a pointer to the matrix (<TT>mod2sparse*</TT>) and a row or column index, starting at zero. The other macrostake as their arguments a pointer to an entry (<TT>mod2entry *</TT>)within some matrix.<BLOCKQUOTE><PRE>mod2sparse_first_in_row(m,i) /* Returns the first entry in row i of m */mod2sparse_first_in_col(m,j) /* Returns the first entry in column j of m */mod2sparse_last_in_row(m,i) /* Returns the last entry in row i of m */mod2sparse_last_in_col(m,j) /* Returns the last entry in column j of m */mod2sparse_next_in_row(e) /* Returns the entry after e in its row */mod2sparse_next_in_col(e) /* Returns the entry after e in its column */mod2sparse_prev_in_row(e) /* Returns the entry before e in its row */mod2sparse_prev_in_col(e) /* Returns the entry before e in its col */mod2sparse_row(e) /* Returns the row index of entry e */mod2sparse_col(e) /* Returns the column index of entry e */mod2sparse_at_end(e) /* Returns 1 if e is a special entry obtained by moving past the end, returns 0 otherwise */</PRE></BLOCKQUOTE><A NAME="alloc-sec"><P><HR><CENTER><BIG>Allocating and Freeing Sparse Modulo-2 Matrices</BIG></CENTER></A><A NAME="allocate"><HR><B>mod2sparse_allocate</B>: Allocate space for a sparse module-2 matrix.</A><BLOCKQUOTE><PRE>mod2sparse *mod2sparse_allocate ( int n_rows, /* Number of rows in matrix */ int n_cols /* Number of columns in matrix */)</PRE></BLOCKQUOTE>Allocates space for a matrix with the given number of rows andcolumns, and returns a pointer to it. The matrix will initiallybe all zero. <P>If there is not enough memory available, a message is displayed onstandard error and the program is terminated. The matrix should befreed with <A HREF="#free"><TT>mod2sparse_free</TT></A> once it is nolonger in use.<P><A NAME="free"><HR><B>mod2sparse_free</B>: Free the space occupied by a sparse module-2 matrix.</A><BLOCKQUOTE><PRE>void mod2sparse_free ( mod2sparse *m /* Pointer to matrix to free */)</PRE></BLOCKQUOTE>Frees the space occupied by the matrix for re-use. The pointer passedshould not be used afterward. Note that space for the individual matrixelements (but not the matrix as a whole) is also freed when <AHREF="#clear"><TT>mod2sparse_clear</TT></A> is called, or the matrixis used as the destination for other operations.<A NAME="copy-clear-sec"><P><HR><CENTER><BIG>Copying and Clearing Sparse Modulo-2 Matrices</BIG></CENTER></A><A NAME="clear"><HR><B>mod2sparse_clear</B>: Set all elements of a matrix to zero.</A><BLOCKQUOTE><PRE>void mod2sparse_clear( mod2sparse *m /* Pointer to matrix to clear */)</PRE></BLOCKQUOTE>Sets all of the elements of the matrix passed to 0. The space occupiedby the previous non-zero elements is freed for use in other matrices, orother purposes. The matrix itself is not freed, however. To do that,use <A HREF="#free"><TT>mod2sparse_free</TT></A>.<P><A NAME="copy"><HR><B>mod2sparse_copy</B>: Copy the contents of one matrix to another.</A><BLOCKQUOTE><PRE>void mod2sparse_copy( mod2sparse *m /* Pointer to matrix to copy from */ mod2sparse *r /* Pointer to matrix to receive data */)</PRE></BLOCKQUOTE>Copies the contents of the first matrix passed, <B>m</B>, to thesecond matrix passed, <B>r</B>, which must already have beenallocated, and must have at least as many rows and columns as thefirst. If <B>r</B> is larger than <B>m</B>, its elements that haverow or column indexes greater than the dimension of <B>m</B> are setto zeros. <P>The space occupied by the previous non-zero entries of <B>r</B> isfreed for general use (which may include being reused immediately forthe copies of the entries in <B>m</B>).<P><A NAME="copyrows"><HR><B>mod2sparse_copyrows</B>: Copy selected rows from one matrix to another.</A><BLOCKQUOTE><PRE>void mod2sparse_copyrows( mod2sparse *m, /* Pointer to matrix to copy rows from */ mod2sparse *r, /* Pointer to matrix in which to store data */ int *rows /* Indexes of rows, numbered from 0 */)</PRE></BLOCKQUOTE>Copies selected rows of the first matrix, <B>m</B>, to the secondmatrix, <B>r</B>, which must already have been allocated, and whichmust have at least as many columns as <B>m</B>. The indexes of therows to copy are given in order as an array of length the same asthe number of rows in <B>r</B>; duplicates are allowed. Rowindexes start at 0. These rows are copied to <B>r</B>, with therow indexed by the first entry in <B>rows</B> going to thefirst row of <B>r</B>, and so forth. If <B>r</B> has more columns than <B>m</B>, the extra entries in each row are set to zeros.<P>The space occupied by the previous non-zero entries of <B>r</B> isfreed for general use (which may include being reused immediately forthe copies of the entries in <B>m</B>).<P><A NAME="copycols"><HR><B>mod2sparse_copycols</B>: Copy selected columns from one matrix to another.</A><BLOCKQUOTE><PRE>void mod2sparse_copycols( mod2sparse *m, /* Pointer to matrix to copy columns from */ mod2sparse *r, /* Pointer to matrix in which to store data */ int *cols /* Indexes of columns, numbered from 0 */)</PRE></BLOCKQUOTE>Copies selected columns of the first matrix, <B>m</B>, to the secondmatrix, <B>r</B>, which must already have been allocated, and whichmust have at least as many rows as <B>m</B>. The indexes of thecolumns to copy are given in order as an array of length the same asthe number of columns in <B>r</B>; duplicates are allowed. Columnindexes start at 0. These columns are copied to <B>r</B>, with thecolumn indexed by the first entry in <B>cols</B> going to thefirst column of <B>r</B>, and so forth. If <B>r</B> has more rows than <B>m</B>, the extra entries in each column are set to zeros.<P>The space occupied by the previous non-zero entries of <B>r</B> isfreed for general use (which may include being reused immediately forthe copies of the entries in <B>m</B>).<A NAME="input-output-sec"><P><HR><CENTER><BIG>Input and Output of Sparse Modulo-2 Matrices</BIG></CENTER></A><A NAME="print"><HR><B>mod2sparse_print</B>: Print a sparse modulo-2 matrix in human-readable form.</A><BLOCKQUOTE><PRE>void mod2sparse_print( FILE *f, /* File to print to */ mod2sparse *m /* Pointer to matrix to print */)</PRE></BLOCKQUOTE>The matrix is printed on standard output with one line of output per row,of the form<BLOCKQUOTE><PRE><I>row</I>: <I>col col col ...</I></PRE></BLOCKQUOTE>where <I>row</I> is the index of the row, and the <I>col</I> entries are the indexes of columns that are non-zero in that row. Row and columnindexes start at zero. Rows with no entries are printed with no columnindexes after the colon. The number of columns is not indicated in the output. <P><A NAME="write"><HR><B>mod2sparse_write</B>: Write a sparse modulo-2 matrix to a file in machine-readable format.</A><BLOCKQUOTE><PRE>int mod2sparse_write( FILE *f, /* File to write data to */ mod2sparse *m /* Pointer to matrix write out */)</PRE></BLOCKQUOTE>Writes a machine-readable representation the sparse matrix <B>m</B> tothe file <B>f</B>. The file should have been opened in binary mode(with a "b" in the mode passed to fopen). The contents written willnot be text, and will not be human-readable. Other binary data mayprecede or follow the data for the matrix written. <P>The data written to the file starts with the number of rows and thenumber of columns. Following this are negative integers giving rowindexes (starting at 1), which apply until the next row index, andpositive integers giving column indexes (starting at 1) for a non-zeroentry in the matrix. The data should be readable by <AHREF="#read"><TT>mod2sparse_read</TT></A> even on a machine with adifferent byte-ordering.<P>The value returned by <TT>mod2sparse_write</TT> is one if theoperation was successful, zero if an error of some sort occurred.<P><A NAME="read"><HR><B>mod2sparse_read</B>: Read a sparse modulo-2 matrix from a file.</A><BLOCKQUOTE><PRE>mod2sparse *mod2sparse_read( FILE *f, /* File to read data from */)</PRE></BLOCKQUOTE>Reads a sparse modulo-2 matrix from the file <B>f</B>. This fileshould have been opened in binary mode (with a "b" in the mode passedto fopen). The contents of the file at the point when<TT>mod2sparse_read</TT> is called should have been written by <AHREF="#write"><TT>mod2sparse_write</TT></A>. Other binary data mayprecede or follow this data.<P>The value returned is a pointer to the matrix read, for which spacewill have been allocated by <TT>mod2sparse_read</TT>, or zero if anerror occurred (either an error reading the file, or data not in theright format).<A NAME="elementary-sec"><P><HR><CENTER><BIG>Elementary Operations on Sparse Modulo-2 Matrices</BIG></CENTER></A><A NAME="find"><HR><B>mod2sparse_find</B>: Look for an entry at a given row and column.</A><BLOCKQUOTE><PRE>mod2entry *mod2sparse_find( mod2sparse *m, /* Matrix in which to look for entry */ int row, /* Row index (from 0) */ int col /* Column index (from 0) */)</PRE></BLOCKQUOTE>Looks for an entry at the given row and column in the matrix <B>m</B>,representing a non-zero element (ie, one with value 1). Returns apointer to this entry if it exists, or zero (a null pointer) if it does not exist (ie, if that element of the matrix has value 0).<P>The search strategy is to first look at the end of the row and theend of the column. The entry might be found at one of these twoplaces, or it might be determinable from these end entries that noentry exists at the given row and column. Otherwise, searches aredone from the start of the row and the start of the column, inparallel, until an entry with the given row and column are found, oruntil it can be determined that such an entry does not exist.Searching in parallel ensures that the operation will be fast if⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -