Title :
The Vertex-Cut Bound and its applications
Author_Institution :
Dept. of Math. & Stat., Queen´´s Univ., Kingston, ON
Abstract :
We introduce the vertex-cut bound as a tool for analyzing the constraint complexity of realizations of a given code on an arbitrary graph. We then use this bound to obtain non-trivial lower bounds on the constraint complexity of such realizations. Our bounds enable us to show, for example, that codes that are good from an error-correcting standpoint cannot have cycle-free realizations with low constraint complexity.
Keywords :
error correction codes; graph theory; arbitrary graph; constraint complexity; cycle-free realization; error-correcting code; vertex-cut bound; Decoding; Graph theory; Graphical models; Information theory; Linear code; Mathematics; Parity check codes; Statistics; Sum product algorithm; Turbo codes;
Conference_Titel :
Information Theory and Its Applications, 2008. ISITA 2008. International Symposium on
Conference_Location :
Auckland
Print_ISBN :
978-1-4244-2068-1
Electronic_ISBN :
978-1-4244-2069-8
DOI :
10.1109/ISITA.2008.4895506
