www.PseudoCodewords.info
All Papers
This page lists papers on pseudo-codewords and topics related to
pseudo-codewords. Note that the assignment of a paper to a certain
category is not always clear-cut and sometimes arbitrary.
Any suggestions for additions to this page are highly
welcome. Please send an email to
Pascal Vontobel
[email: firstname dot lastname at hp dot com].
Thank you!
Papers on Pseudo-Codewords
2009
N. Axvig, D. Dreher, K. Morrison, E. Psota, L.C. Perez, and J.L. Walker
Analysis of connections between pseudocodewords [ieeexplore]
IEEE Trans. Inf. Theory, vol. 55, no. 9, pp. 4099-4107, Sept. 2009.
K. Chilappagari, M. Chertkov, M. Stepanov, and B. Vasic
Instanton-based techniques for analysis and reduction of error floors of LDPC codes [ieeexplore]
J. Sel. Areas in Comm., vol. 27, no. 6, pp. 855-865, Aug. 2009.
R. Smarandache and P.O. Vontobel
Absdet-pseudo-codewords and perm-pseudo-codewords: definitions and properties [ieeexplore]
Proc. IEEE Int. Symp. Information Theory, Seoul, Korea, pp. 229-233, June 28-July 3, 2009.
R. Smarandache, A.E. Pusane, P.O. Vontobel, and D.J. Costello, Jr.
Pseudocodeword performance analysis for LDPC convolutional codes [ieeexplore]
IEEE Trans. on Inf. Theory, vol. 55, no. 6, pp. 2577-2598, Jun. 2009.
D. Dreher and J. Walker
Connections between computation trees and graph covers [ieeexplore]
Proc. Information Theory and Applications Workshop, UC San Diego, La Jolla, CA, USA, February 8-13, 2009.
P.O. Vontobel
A graph-dynamics interpretation of the sum-product algorithm [slides]
Proc. Information Theory and Applications Workshop, UC San Diego, La Jolla, CA, USA, Feb. 8-13 2009.
2008
S. Matsuda, S. Saito, and T. Hiramatsu
Computation of zeta functions counting pseudo-codewords of linear codes [ieeexplore]
Proc. Intern. Symp. Inform. Theory and its Appl., Auckland, New Zealand, Dec. 7-10, 2008.
N. Axvig, D. Dreher, K. Morrison, E. Psota, L.C. Pérez, and J. Walker
Towards universal cover decoding [pdf]
Proc. 2008 International Symposium on Information Theory and its Applications, Auckland, New Zealand; Dec. 2008.
M. Chertkov
Exactness of belief propagation for some graphical models with loops [IOP]
J. Stat. Mech., P10016, Oct. 2008
P.O. Vontobel
Symbolwise graph-cover decoding: connecting sum-product algorithm decoding and Bethe free energy minimization
[ieeexplore] [slides]
Proc. 46th Allerton Conf. on Communications, Control, and Computing, Allerton House, Monticello, IL, USA, Sept. 23-26, 2008.
N. Axvig, D. Dreher, K. Morrison, E. Psota, L.C. Pérez, and J. Walker
Average min-sum decoding of LDPC codes [pdf]
Proc. 5th Intern. Symp. on Turbo Codes and Related Topics, Lausanne, Switzerland, Sept. 1-5, 2008.
M. Miwa, T. Wadayama, and I. Takumi
A cutting plane method based on redundant rows for improving fractional distance [arxiv]
Proc. 5th Intern. Symp. on Turbo Codes and Rel. Topics, Lausanne, Switzerland, Sept. 1-5, 2008.
V. Skachek and M.F. Flanagan
Lower bounds on the minimum pseudodistance for linear Codes with q-ary PSK modulation over AWGN [arxiv]
Proc. 5th International Symposium on Turbo Codes and Related Topics, Lausanne, Switzerland, September 1-5, 2008.
C.A. Kelley and J.L. Walker
LDPC codes from voltage graphs [ieeexplore]
Proc. IEEE Intern. Symp. Inform. Theory, Toronto, Canada, pp. 792-796, July 6-11, 2008.
N. Axvig, D. Dreher, K. Morrison, E. Psota, L.C. Pérez, and J. Walker
A universal theory of decoding and pseudocodewords [pdf]
SGER Technical report, July 2008.
M. Chertkov and M.G. Stepanov
An efficient pseudo-codeword search algorithm for linear programming decoding of LDPC codes [ieeexplore]
IEEE Transactions on Information Theory, vol. IT-54, no. 4, pp. 1514-1520, Apr. 2008.
S.-T. Xia and F.-W. Fu
Minimum pseudoweight and minimum pseudocodewords of LDPC codes [ieeexplore]
IEEE Transactions on Information Theory, vol. IT-54, no. 1, pp. 480-485, Jan. 2008.
2007
E. Mo and M.A. Arman
Design and performance of LDPC codes extended with parity-check symbols from a larger alphabet [ieeexplore]
Proc. IEEE Intern. Conf. on Information, Communications, and Signal Processing, Dec. 10-13., 2007
C. Kelley and D. Sridhara
Pseudocodewords of Tanner graphs [ieeexplore]
IEEE Trans. Inform. Theory, vol. 53, no. 11, pp. 4013-4038, Nov. 2007.
N. Axvig, D. Dreher, K. Morrison, E. Psota, L.C. Pérez, and J. Walker,
A universal theory of decoding and pseudocodewords [pdf]
Proc. 45th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA, Sept. 25-28, 2007.
C.A. Kelley and D. Sridhara
On the pseudocodeword weight and parity-check matrix redundancy of linear codes [ieeexplore]
Proc. IEEE Information Theory Workshop, Lake Tahoe, CA, USA, Sept. 2007.
M. Chertkov
Reducing the error floor [ieeexplore]
Proc. Information Theory Workshop, Lake Tahoe, CA, USA, Sept. 2007.
C.A. Kelley and D. Sridhara
Eigenvalue bounds on the pseudo-codeword weight of expander codes [AIMsciences]
Adv. Math. Comm., vol. 1, no. 3, pp. 287-307, Aug. 2007.
E. Rosnes
On the effects of pseudo-codewords on independent rayleigh flat-fading channels [ieeexplore]
Proc. IEEE Information Theory Workshop, Bergen, Norway, July 2007.
R. Smarandache and P.O. Vontobel
Pseudo-codeword analysis of Tanner graphs from projective and Euclidean planes [ieeexplore]
IEEE Trans. Inform. Theory, vol. IT-53, no. 7, pp. 2376-2393, July 2007.
P.A. Regalia and J.M. Walsh
Optimality and duality of the turbo decoder [ieeexplore]
Proceedings of the IEEE, vol. 95, no. 6, pp. 1362-1377, Jun. 2007.
V.Y. Chernyak and M. Chertkov
Loop calculus and belief propagation for q-ary alphabet: loop tower [ieeexplore]
Proc. IEEE Intern. Symp. Inform. Theory, Nice, France, pp. 316-320, June 24-29, 2007.
M. Chertkov and M. Stepanov
Pseudo-codeword landscape [ieeexplore]
Proc. IEEE Intern. Symp. Inform. Theory, Nice, France, pp. 1546-1550, June 24-29, 2007.
C. Kelley, D. Sridhara, and J. Rosenthal,
Tree-based construction of LDPC codes having good pseudocodeword weights [ieeexplore]
IEEE Trans. Inform. Theory, vol. 53, no. 4, pp. 1460-1478, Apr. 2007.
M. Chertkov and M. Stepanov
Searching for low weight pseudo-codewords [arxiv]
Proc. ITA Workshop, San Diego, CA, USA, Jan./Feb. 2007.
2006
J.M. Walsh, P.A. Regalia, and C.R. Johnson, Jr.
Turbo decoding as iterative constrained maximum-likelihood sequence detection [ieeexplore]
IEEE Transactions on Information Theory, vol. IT-52, no. 12, pp. 5426--5437, Dec. 2006.
S.-T. Xia and F.-W. Fu
Minimum pseudo-codewords of LDPC codes [ieeexplore]
IEEE Inform. Theory Workshop, Chengdu, China, pp. 109-113, Oct. 2006.
M.G. Stepanov and M. Chertkov
Improving convergence of Belief Propagation decoding [arxiv]
C.A. Kelley, D. Sridhara, and J. Rosenthal
Pseudocodeword weights for non-binary LDPC codes [ieeexplore]
Proc. IEEE Intern. Symp. Inform. Theory, Seattle, WA, USA, pp. 1379-1383, July 9-14, 2006.
R. Smarandache, A.E. Pusane, P.O. Vontobel, and D.J. Costello, Jr.
Pseudo-codewords in LDPC convolutional codes [.pdf]
Proc. IEEE Intern. Symp. on Inform. Theory, Seattle, WA, USA, pp. 1364 - 1368, July 9 - 14, 2006.
R. Koetter, W.-C. W. Li, P.O. Vontobel, and J.L. Walker
Characterizations of pseudo-codewords of LDPC codes [arxiv]
accepted (after revisions) for Advances in Mathematics, Aug. 2006.
S.-T. Xia and F.-W. Fu
On the stopping distance of finite geometry LDPC codes [ieeexplore]
IEEE Comm. Letters, vol. 10, no. 5, pp. 381-383, May 2006.
M. Chertkov and M.G. Stepanov
An efficient pseudo-codeword search algorithm for linear programming decoding of LDPC codes [arxiv]
www.arxiv.org, Jan. 2006.
2005
P.O. Vontobel and R. Koetter
Graph-cover decoding and finite-length analysis of message-passing iterative decoding of LDPC codes [arxiv]
accepted for IEEE Trans. on Inform. Theory, May 2007.
R. Smarandache and M. Wauer.
Bounds on the pseudo-weight of minimal pseudo-codewords of projective geometry codes [arxiv]
submitted, Oct. 2005.
D. Sridhara, C. Kelley, and J. Rosenthal
Tree-based construction of LDPC codes [ieeexplore]
Proc. IEEE Intern. Symp. on Inform. Theory, Adelaide, Australia, pp. 845-849, Sep. 4-9, 2005.
P.O. Vontobel and R. Smarandache
On minimal pseudo-codewords of Tanner graphs from projective planes [arxiv]
Proc. 43rd Allerton Conf. on Communications, Control, and Computing, Allerton House, Monticello, Illinois, USA, Sept. 28-30, 2005.
D. Haley and A. Grant
Improved reversible LDPC codes [ieeexplore]
Proc. IEEE Intern. Symp. on Inform. Theory 2005, Adelaide, Australia, pp. 1367-1371, Sept. 4 - 9, 2005.
P. Chaichanavong and P. H. Siegel
Relaxation bounds on the minimum pseudo-weight of linear block codes [arxiv]
Proc. IEEE Intern. Symp. on Inform. Theory, Adelaide, Australia, pp. 805-809, September 4-9, 2005.
P.O. Vontobel, R. Smarandache, N. Kiyavash, J. Teutsch, and D. Vukobratovic
On the minimal pseudo-codewords of codes from finite geometries [arxiv]
Proc. IEEE Intern. Symp. on Inform. Theory 2005, Adelaide, Australia, pp. 980-984, Sept. 4 - 9, 2005.
Z. Zhang
Study of permutation matrices based LDPC code construction [.pdf]
Project Report, UC Berkeley, 2005.
A. Gueye
Toward the weight enumerator function of pseudo-codewords [.pdf]
Project Report, UC Berkeley, 2005.
2004
R. Koetter, W.-C. W. Li, P.O. Vontobel, and J.L. Walker
Pseudo-codewords of cycle codes via zeta functions [arxiv]
Proc. IEEE Inform. Theory Workshop, San Antonio, TX, USA, pp. 6-12, October 24-29, 2004.
C. Kelley and D. Sridhara
Structure of pseudocodewords in Tanner graphs [.pdf]
Proc. Intern. Symp. on Inform. Theory and its Appl. Oct. 10-13, 2004.
P.O. Vontobel and R. Koetter
Lower bounds on the minimum pseudo-weight of linear codes
Final version: [.pdf] Submitted version (with addtional details): [.pdf]
Proc. IEEE Intern. Symp. Inform. Theory, Chicago, IL, USA, p. 70, June 27 - July 2, 2004.
C. Kelley, D. Sridhara, J. Xu, and J. Rosenthal
Pseudocodeword weights and stopping sets [ieeexplore]
Proc. IEEE Intern. Symp. on Inform. Theory, Chicago, IL, USA, p. 150, June 27 - July 3, 2004.
2003
T.D. Coleman
Pseudocodewords presentation [.pdf]
Technical Report, M.I.T., Cambridge, MA, USA, Sep. 2003.
R. Koetter and P.O. Vontobel
Graph covers and iterative decoding of finite-length codes [.pdf]
Proc. 3rd International Symposium on Turbo Codes & Related Topics, Brest, France, pp. 75-82, Sep. 1-5, 2003.
2001
G.D. Forney, Jr., R. Koetter, F.R. Kschischang, and A. Reznik
On the effective weights of pseudocodewords for codes defined on graphs with cycles [citeseer]
in Codes, Systems, and Graphical Models (B. Marcus and J. Rosenthal, eds.), vol. 123 of IMA Vol. Math. Appl., pp. 101-112, Springer Verlag, New York, Inc., 2001.
B. Frey, R. Koetter, and A. Vardy,
Signal-space characterization of iterative decoding [ieeexplore]
IEEE Trans. on Inform. Theory, vol. IT-47, no. 2, pp. 766-781, Feb 2001.
1999
G.A. Horn
Iterative Decoding and Pseudocodewords
PhD thesis, California Institute of Technology, Pasadena, CA, USA, 1999.
1998
S. Aji, G. Horn, R. McEliece, and M. Xu
Iterative Min-Sum Decoding of Tail-biting Codes [ieeexplore]
Proc. IEEE Inform. Theory Workshop, Killarny, Ireland, pp. 68-69, June 22-26, 1998.
1996
N. Wiberg
Codes and Decoding on General Graphs [.pdf]
Linköping Studies in Science and Technology, Ph.D thesis No. 440, Linköping, Sweden, 1996.
Papers on Linear Programming Decoding
2009
A.G. Dimakis and P.O. Vontobel
LP decoding meets LP decoding: a connection between channel coding and compressed sensing [arxiv]
Proc. of the 47th Allerton Conference on Communications, Control, and Computing, Allerton House, Monticello, Illinois, USA, Sep. 30 - Oct. 2, 2009.
M.F. Flanagan, V. Skachek, E. Byrne, and M. Greferath
Linear-programming decoding of nonbinary linear codes [ieeexplore]
IEEE Trans. Inf. Theory, vol. 55, no. 9, pp. 4134-4154, Sept. 2009.
A.G. Dimakis, A.A. Gohari, and M.J. Wainwright
Guessing facets: polytope structure and improved LP decoder [ieeexplore]
IEEE Trans. Inf. Theory, vol. 55, no. 8, pp. 3479-3487, Aug. 2009.
M. Miwa, T. Wadayama, and I. Takumi
A cutting-plane method based on redundant rows for improving fractional distance [ieeexplore]
IEEE J. Selected Areas in Comm., vol. 27, no. 6, pp. 1005-1012, Aug. 2009.
E. Rosnes
On the pairwise error probability of linear programming decoding on independent Rayleigh flat-fading channels [ieeexplore]
IEEE Trans. Inform. Theory, vol. IT-55, no. 7, pp. 2942-2955, July 2009.
S. Heupel
Cycle polytopes and their application in coding theory [.pdf]
MSc. Thesis, Technical University Kaiserslautern, Germany, July 2009.
T. Wadayama
An LP decoding algorithm based on primal path-following interior point method [ieeexplore]
Proc. IEEE Int. Symp. Information Theory, Seoul, Korea, pp. 389-393, June 28-July 3, 2009.
V. Skachek
On LP decoding of nonbinary expander codes [ieeexplore]
Proc. IEEE Int. Symp. Information Theory, Seoul, Korea, pp. 384 - 388, June 28-July 3, 2009.
S. K. Chilappagari, B. Vasic, M. Stepanov, and M. Chertkov
Analysis of error floors of LDPC codes under LP decoding over the BSC [ieeexplore]
Proc. IEEE Int. Symp. Information Theory, Seoul, Korea, pp. 379-383, June 28-July 3, 2009.
S. Arora, C. Daskalakis, and D. Steurer
Message passing algorithms and improved LP decoding [acm]
Proc. 41st Annual ACM Symposium on Theory of Computing (STOC), Bethesda, MD, USA, May 31 - June 2, 2009.
M.F. Flanagan
A unified framework for linear-programming based communication receivers [arxiv]
submitted, Feb. 2009.
2008
M.H. Taghavi, A. Shokrollahi, and P.H. Siegel
Efficient implementation of linear programming decoding [arxiv]
submitted to IEEE Transactions on Information Theory, Dec. 2008.
M.-H. Taghavi N. and P.H. Siegel
Adaptive methods for linear programming decoding [ieeexplore]
IEEE Trans. Inform. Theory, vol. 54, no. 12, pp. 5396-5410, Dec. 2008.
A. Tanatmis, S. Ruzika, H.W. Hamacher, M. Punekar, F. Kienle, and N. Wehn
A separation algorithm for improved LP-decoding of linear block codes [arxiv]
submitted to IEEE Transactions on Information Theory, Dec. 2008.
M. Lunglmayr, J. Berkmann, and M. Huemer
LP decoding of LDPC codes in HARQ systems [ieeexplore]
Proc. 6th International Symposium on Communication Systems, Networks, and Digital Signal Processing, pp. 535-539, July 25, 2008.
A. Cohen, F. Alajaji, N. Kashyap, and G. Takahara,
LP Decoding for joint source-channel codes and for the non-ergodic Polya channel [ieeexplore]
IEEE Comm. Letters, vol. 12, no. 9, pp. 678-680, Sept. 2008.
M. F. Flanagan
Linear-Programming Receivers [arxiv]
Proc. 46th Annual Allerton Conference on Communication, Control and Computing, Monticello, Illinois, September 23-26, 2008.
M. Miwa, T. Wadayama, I. Takumi
A cutting plane method based on redundant rows for improving fractional distance [ieeexplore]
Proc. 5th International Symposium on Turbo Codes and Related Topics, Lausanne, Switzerland, pp. 43-48, Sept. 1-5, 2008.
A. Tanatmis, S. Ruzika, H.W. Hamacher, M. Punekar, F. Kienle, and N. Wehn
A separation algorithm for improved LP-decoding of linear block codes [ieeexplore]
Proc. 5th International Symposium on Turbo Codes and Related Topics, Lausanne, Switzerland, pp. 37-42, Sept. 1-5, 2008.
T. Wadayama
Interior point decoding for linear vector channels based on convex optimization [ieeexplore]
Proc. IEEE Intern. Symp. Inform. Theory, Toronto, Canada, pp. 1493-1497, July 6-11, 2008.
D. Burshtein
Linear complexity approximate LP decoding of LDPC codes: Generalizations and improvements [ieeexplore]
Proc. 5th International Symposium on Turbo Codes and Related Topics, Lausanne, Switzerland, pp. 31-36, Sept. 1-5, 2008.
S.K. Chilappagari, M. Chertkov, and B. Vasic
Provably efficient instanton search algorithm for LP decoding of LDPC codes over the BSC [arxiv]
submitted to IEEE Transactions on Information Theory, Aug. 2008.
C. Daskalakis, A.G. Dimakis, R.M. Karp, and M.J. Wainwright
Probabilistic analysis of linear programming decoding [ieeexplore]
IEEE Trans. Inform. Theory, vol. 54, no. 8, pp. 3565-3578, Aug. 2008.
N. Kashyap
A decomposition theory for binary linear codes [ieeexplore]
IEEE Trans. Inform. Theory, vol. IT-54, no. 7, pp. 3035-3058, July 2008.
V. Skachek, M.F. Flanagan, E. Byrne, and M. Greferath
Polytope representations for linear-programming decoding of non-binary linear codes [ieeexplore]
Proc. IEEE Intern. Symp. Inform. Theory, Toronto, Canada, pp. 1508-1512, July 6-11, 2008.
M.F. Flanagan
Codeword-independent performance of nonbinary linear codes under linear-programming and sum-product decoding [arxiv]
Proc. IEEE International Symposium on Information Theory (ISIT 2008), Toronto, Canada, July 6-11, 2008.
D. Burshtein
Iterative approximate linear programming decoding of LDPC codes with linear complexity [ieeexplore]
Proc. IEEE Intern. Symp. Inform. Theory, Toronto, Canada, pp. 1498-1502, July 6-11, 2008.
P.O. Vontobel
Interior-point algorithms for linear-programming decoding [arxiv]
Proc. Information Theory and its Applications Workshop, UC San Diego, La Jolla, CA, USA, Jan./Feb., 2008.
M.F. Flanagan, V. Skachek, E. Byrne, and M. Greferath
Linear-programming decoding of non-binary linear codes [arxiv]
Proc. 7-th International ITG Conference on Source and Channel Coding (SCC'08), Ulm, Germany, Jan. 2008.
2007
K. Yang, X. Wang, and J. Feldman
Fast ML decoding of SPC product code by linear programming decoding [ieeexplore]
Proc. IEEE GLOBECOM, Washington, DC, USA, pp. 1577-1581, Nov. 2007.
S.C. Draper, J.S. Yedidia, and Y. Wang
ML decoding via mixed-integer adaptive linear programming [MERL]
Proc. IEEE Intern. Symp. on Inform. Theory, June 2007.
T. Wadayama
Interior point decoding for linear vector channels [arxiv]
submitted, May 2007.
J. Feldman, T. Malkin, R.A. Servedio, C. Stein, and M.J. Wainwright
LP decoding corrects a constant fraction of errors [ieeexplore]
IEEE Trans. Inform. Theory, vol. 53, no. 1, pp. 82-89, Jan. 2007.
2006
M. Chertkov and V.Y. Chernyak
Loop calculus helps to improve belief propagation and linear programming decodings of low-density-parity-check codes [arxiv]
Proc. 44th Annual Allerton Conf. on Communications, Control and Computing, Monticello, IL, USA, Sep. 27-29, 2006.
K. Yang, J. Feldman, X. Wang
Nonlinear programming approaches to decoding low-density parity-check codes [ieeexplore]
IEEE J. Sel. Areas in Comm., vol. 24, no. 8, pp. 1603-1613, Aug. 2006.
A.G. Dimakis and M.J. Wainwright
Guessing facets: polytope structure and improved LP decoder [ieeexplore]
Proc. IEEE Intern. Symp. on Inform. Theory, Seattle, WA, pp. 1369-1373, July 2006.
P.O. Vontobel and R. Koetter
Towards low-complexity linear-programming decoding [arxiv]
Proc. 4th Intern. Conf. on Turbo Codes and Related Topics, Munich, Germany, Apr. 3-7, 2006.
P.O. Vontobel and R. Koetter
Bounds on the threshold of linear programming decoding [arxiv]
Proc. IEEE Inform. Theory Workshop, Punta Del Este, Uruguay, Mar. 13-16, 2006.
R. Koetter and P.O. Vontobel
On the block error probability of LP decoding of LDPC codes [arxiv]
Proc. Inaugural Workshop of the Center for Information Theory and its Applications, UCSD, La Jolla, CA, USA, Feb. 6-10, 2006.
M. Chertkov and M.G. Stepanov,
Looping linear programming decoding of LDPC codes [arxiv]
submitted to IEEE Trans. on Inform. Theory, Jan. 2006.
M.H. Taghavi N. and P.H. Siegel
Adaptive linear programming decoding [arxiv]
Proc. IEEE Intern. Symp. on Inform. Theory 2006, Seattle, WA, USA, July 9 - 14, 2006.
2005
J. Feldman, R. Koetter, and P.O. Vontobel
The benefit of thresholding in LP decoding of LDPC codes [arxiv]
Proc. IEEE Intern. Symp. on Inform. Theory 2005, Adelaide, Australia, pp. 307-311, Sept. 4-9, 2005.
J. Feldman, M.J. Wainwright, and D.R. Karger
Using linear programming to decode binary linear codes [ieeexplore]
IEEE Trans. on Inform. Theory, vol. IT-51, no. 3, pp. 954-972, Mar. 2005.
J. Feldman and C. Stein
LP decoding achieves capacity [acm]
Symposium on Discrete Algorithms (SODA '05), Vancouver, Canada, Jan. 23-25, 2005.
N. Halabi and G. Even
Improved bounds on the word error probability of RA(2) codes with linear-programming-based decoding [ieeexplore]
IEEE Trans. on Inform. Theory, vol. IT-51, no. 1, pp. 265-280, Jan. 2005.
2004
P.O. Vontobel and R. Koetter
On the relationship between linear programming decoding and min-sum algorithm decoding [.pdf]
Proc. ISITA 2004, Parma, Italy, p. 991-996, October 10-13, 2004.
(A typo on page 1 has been corrected: "max-sum" -> "min-sum".)
J. Feldman, T. Malkin, C. Stein, R.A. Servedio, and M.J. Wainwright
LP decoding corrects a constant fraction of errors [.pdf]
Proc. IEEE Intern. Symp. on Inform. Theory, Chicago, IL, USA, p. 68, June 27-July 2, 2004.
J. Feldman and D.R. Karger
Decoding turbo-like codes via linear programming [ScienceDirect]
Journal of Computer and System Sciences (FOCS '02 Special Issue), vol. 68, no. 4, pp. 733-752, June 2004.
2003
J. Feldman, D.R. Karger, and M.J. Wainwright
LP decoding [.pdf]
Proc. 41st Allerton Conf. on Communications, Control, and Computing, Monticello, IL, USA, October 1-3, 2003.
J. Feldman
Decoding Error-Correcting Codes via Linear Programming [.pdf]
PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, 2003.
J. Feldman, D.R. Karger, and M.J. Wainwright
Using linear programming to decode linear codes [.pdf]
Proc. 37th annual Conference on Information Sciences and Systems (CISS '03), Baltimore, MD, USA, Mar. 12-14, 2003.
M.J. Wainwright and M.I. Jordan
Variational inference in graphical models: the view from the marginal polytope [.ps]
Proc. 41st Allerton Conf. on Communications, Control, and Computing, Monticello, IL, USA, Oct. 1-3, 2003.
2002
J. Feldman and D.R. Karger
Decoding turbo-like codes via linear programming [ieeexplore]
Proc. 43rd Annual IEEE Symp. Found. of Comp. Sci., pp. 251-260, Nov. 16-19, 2002
J. Feldman, D.R. Karger, and M.J. Wainwright
Linear programming-based decoding of turbo-like codes and its relation to iterative approaches [.pdf]
Proc. 40th Allerton Conf. on Communications, Control, and Computing, Monticello, IL, USA, October 2-4, 2002.
Papers on Stopping Sets, Near-Codewords, Instantons, Trapping Sets, and Absorbing Sets
2008
T. Wadayama
Average stopping set weight distributions of redundant random ensembles [ieeexplore]
IEEE Trans. Inform. Theory, vol. 54, no. 11, pp. 4991-5004, Nov. 2008.
M. Ivkovic, S.K. Chilappagari, and B. Vasic
Eliminating trapping sets in low-density parity check codes by using Tanner graph covers [ieeexplore]
IEEE Trans on Inf. Theory, vol. 54, no. 8, pp. 3763-3768, Aug. 2008.
P. Lee, L. Dolecek, Z. Zhang, V. Anantharam, B. Nikolic, and M.J. Wainwright
Error floors in LDPC codes: fast simulation, bounds and hardware emulation [ieeexplore]
Proc. IEEE Intern. Symp. Inform. Theory, Toronto, Canada, pp. 444-448, July 6-11, 2008.
G. Sridharan, A. Kumarasubramanian, A. Thangaraj, and S. Bhashyam
Optimizing burst erasure correction of LDPC codes by interleaving [ieeexplore]
Proc. IEEE Intern. Symp. Inform. Theory, Toronto, Canada, pp. 1143-1147, July 6-11, 2008.
V. Rathi
Conditional entropy of non-binary LDPC codes over the BEC [ieeexplore]
Proc. IEEE Intern. Symp. Inform. Theory, Toronto, Canada, pp. 945-949, July 6-11, 2008.
M. Hirotomo, Y. Konishi, and M. Morii
On the probabilistic computation algorithm for the minimum-size stopping sets of LDPC codes [ieeexplore]
Proc. IEEE Intern. Symp. Inform. Theory, Toronto, Canada, pp. 295-299, July 6-11, 2008.
J. Han and P.H. Siegel
On ML redundancy of codes [ieeexplore]
Proc. IEEE Intern. Symp. Inform. Theory, Toronto, Canada, pp. 280-284, July 6-11, 2008.
K.A.S. Abdel-Ghaffar and J.H. Weber
Separating erasures from errors for decoding [ieeexplore]
Proc. IEEE Intern. Symp. Inform. Theory, Toronto, Canada, pp. 215-219, July 6-11, 2008.
M. Hirotomo, Y. Konishi, and M. Morii
A probabilistic algorithm for finding the minimum-size stopping sets of LDPC codes [ieeexplore]
Proc. IEEE Information Theory Workshop, Porto, Portugal, pp. 66-70, May 5-9, 2008.
J.H. Weber and K.A.S. Abdel-Ghaffar
Results on parity-check matrices with optimal stopping and/or dead-end set enumerators [ieeexplore]
IEEE Trans. on Inform. Theory, vol. IT-54, pp. 1368-1374, March 2008.
S.K. Chilappagari, D.V. Nguyen, B. Vasic, and M.W. Marcellin
On the guaranteed error correction capability of LDPC codes [ieeexplore]
Proc. IEEE Intern. Symp. Inform. Theory, Toronto, Canada, pp. 434-438, July 6-11, 2008.
2007
Z. Zhang, L. Dolecek, V. Anantharam, M. Wainwright, and B. Nikolic,
Quantization effects in low-density parity-check decoders [not yet available]
to appear in Proc. ICC 2007, Glasgow, UK, June 2007.
L. Dolecek, Z. Zhang, V. Anantharam, M. Wainwright, and B. Nikolic,
Analysis of absorbing sets for array-based LDPC codes [not yet available]
to appear in Proc. ICC 2007, Glasgow, UK, June 2007.
O. Milenkovic, E. Soljanin, and P. Whiting
Asymptotic spectra of trapping sets in regular and irregular LDPC code ensembles [ieeexplore]
IEEE Trans. Inform. Theory, vol. 53, no. 1, pp. 39-55, Jan. 2007.
2006
Z. Zhang, L. Dolecek, B. Nikolic, V. Anantharam, and M. Wainwright
Investigation of error floors of a structured low-density parity-check code by hardware simulation [.pdf]
Proc. Globecom 2006, San Francisco, CA, USA, Nov. - Dec. 2006.
S.-T. Xia and F.-W. Fu
Stopping set distributions of some linear codes [ieeexplore]
IEEE Inform. Theory Workshop, Chengdu, China, pp. 47-51, Oct. 2006.
M. Stepanov and M. Chertkov
Instanton analysis of low-density parity-check codes in the error-floor regime [ieeexplore]
Proc. IEEE Intern. Symp. on Inform. Theory, Seattly, WA, USA, July 2006, pp. 552-556.
M. Chertkov and V.Y. Chernyak
Loop series for discrete statistical models on graphs [pdf]
J. Stat. Mech, 2006.
M. Chertkov and V.Y. Chernyak
Loop calculus in statistical physics and information science [pdf]
Phys. Rev. E 73.
S.-T. Xia and F.-W. Fu
On the minimum pseudo-codewords of LDPC codes [ieeexplore]
IEEE Comm. Letters, vol. 10, no. 5, pp. 363-365, May 2006.
2005
K.M. Krishnan and P. Shankar
On the complexity of finding stopping distance in Tanner graphs [arxiv]
submitted, 2005.
M. Zhu and K.M. Chugg
Lower bounds on stopping distance of linear codes and their applications [arxiv]
Proc. 43rd Allerton Conf. on Communications, Control, and Computing, Monticello, IL, USA, Sep. 28-30, 2005.
S. Laendner and O. Milenkovic
Algorithmic and combinatorial analysis of trapping sets in structured LDPC codes [arxiv]
Proc. WirelessCom, Hawaii, USA, Jun. 13-16, 2005.
O. Milenkovic, E. Soljanin, and P. Whiting
Asymptotic distributions of trapping sets in random regular LDPC code ensembles [arxiv]
Proc. 43rd Allerton Conf. on Communications, Control, and Computing, Monticello, IL, USA, Sep. 18-20, 2005.
A. Orlitsky, K. Viswananathan, and J. Zhang
Stopping set distribution of LDPC code ensembles [ieeexplore]
IEEE Trans. Inform. Theory, vol. IT-51, no. 3, pp. 929-953, Mar. 2005.
2004
V. Chernyak, M. Chertkov, M. Stepanov, and B Vasic,
Instanton method of post-error-correction analytical evaluation [ieeexplore]
Proc. IEEE Inform. Theory Workshop, San Antonio, TX, USA, Oct. 24-29, 2004, pp. 220-224.
2003
T. Richardson
Error floors of LDPC codes [arxiv]
Proc. 41st Allerton Conf. on Communications, Control, and Computing, Monticello, IL, USA, October 1-3, 2003.
D.J.C. MacKay and M.S. Postol
Weaknesses of Margulis and Ramanujan-Margulis low-density parity-check codes [web]
Electronic Notes in Computer Science, 2003.
N. Kashyap and A. Vardy
Stopping sets in codes from designs,
Conference version: [ieeexplore] Long version (never submitted for publication): [.pdf]
Proc. IEEE Intern. Symp. Inform. Theory, Yokohama, Japan, p. 122, June 29 - July 4, 2003.
2002
C. Di, D. Proietti, T. Richardson, E. Telatar, and R. Urbanke
Finite length analysis of low-density parity-check codes on the binary erasure channel [ieeexplore]
IEEE Trans. Inform. Theory, vol. IT-48, no. 6, pp. 1570-1579, Jun. 2002.
T. Richardson, A. Shokrollahi, and R. Urbanke,
Finite-length analysis of various low-density parity-check ensembles for the binary erasure channel [ieeexplore]
Proc. IEEE International Symposium on Information Theory, Lausanne, Switzerland, p. 1, Jun. 30 - Jul. 5, 2002.
A. Orlitsky, R. Urbanke, K. Vishwanathan, and J. Zhang
Stopping sets and the girth of Tanner graphs [ieeexplore]
Proc. IEEE International Symposium on Information Theory, Lausanne, Switzerland, p. 2, Jun. 30 - Jul. 5, 2002.
Papers on Extrinsic Message Degree (EMD) and Approximate Cycle EMD (ACE)
2008
D. Vukobratovic and V. Senk
Generalized ACE constrained progressive-edge-growth LDPC code design [ieeexplore]
IEEE Communications Letters, Vol.12, No.1, pp. 32-34, January 2008.
2007
D. Vukobratovic, A. Djurendic, and V. Senk
ACE spectrum of LDPC codes and generalized ACE design [ieeexplore]
Proc. ICC 2007, Glasgow, UK, June 2007, pp. 665-670.
2005
S. John and H.M. Kwon
Approximate cycle extrinsic message degree regular quasi circulant LDPC codes [ieeexplore]
Proc. Milcom, pp. 2877-2881, Oct. 17-20, 2005.
2004
H. Xiao and A.H. Banihashemi
Improved progressive-edge-growth (PEG) construction of irregular LDPC codes [ieeexplore]
IEEE Comm. Lett., vol. 8, no. 12, pp. 715-717, Dec. 2004.
W.-Y. Weng, A. Ramamoorthy, and R.D. Wesel
Lowering the error floors of irregular high-rate LDPC codes by graph conditioning [ieeexplore]
Proc. Veh. Tech. Conf. (Fall), pp. 2549-2553, Sep. 26-29, 2004.
T. Tian, C. Jones, J.D. Villasenor, and R.D. Wesel
Selective avoidance of cycles in irregular LDPC code construction [ieeexplore]
IEEE Trans. on Comm., vol. COM-52, no. 8, pp.1242-1247, Aug. 2004.
A. Ramamoorthy and R.D. Wesel
Construction of short block length irregular low-density parity-check codes [ieeexplore]
Proc. IEEE Intern. Conf. Comm., vol. 1, pp. 410-414, Jun. 2004.
2003
T. Tian, C. Jones, J.D. Villasenor, and R.D. Wesel
Construction of irregular LDPC codes with low error floors [ieeexplore]
Proc. IEEE Intern. Conf. Comm., vol. 5, pp. 3125-3129, May 2003.
Papers on High-Density Parity-Check (HDPC) Codes
2009
S. Ouzan and Y. Be'ery
Moderate-density parity-check codes [.pdf]
submitted to IEEE Transactions on Communications, September 2009.
:
I. Dimnik and Y. Be'ery
Improved random redundant iterative HDPC decoding [ieeexplore]
IEEE Transactions on Communications, vol. 57, no. 7, pp. 1982-1985, July 2009.
J.G. Knudsen, C. Riera, L. E. Danielsen, M. G. Parker, and E. Rosnes
Iterative decoding on multiple Tanner graphs using random edge local complementation [arxiv]
Proc. IEEE Int. Symp. Information Theory, Seoul, Korea, June 28-July 3, 2009.
T. Hehn, J.B. Huber, S. Laendner, and O. Milenkovic
Multiple-bases belief-propagation for decoding of short block codes [arxiv]
full paper that accompanies a letter that has bee submitted to IEEE Trans. on Comm., 2009.
2008
S. Sharifi Tehrani, C. Jego, B. Zhu, and W.J. Gross
Stochastic decoding of linear block codes with high-density parity-check matrices [ieeexplore]
IEEE Trans. on Sig. Proc., vol. 56, no. 11, pp. 5733-5739, Nov. 2008.
T.R. Halford and K.M. Chugg
Random redundant iterative soft-in soft-out decoding [ieeexplore]
IEEE Trans. on Comm., vol. 56, no. 4, pp. 513-517, Apr. 2008.
2007
C. Jego and W.J. Gross
Turbo decoding of product codes based on the modified adaptive belief propagation algorithm [ieeexplore]
Proc. IEEE Intern. Symp. Inform. Theory, Nice, France, pp. 641-644, June 24-29, 2007.
T. Hehn, J.B. Huber, S. Laendner, and O. Milenkovic
Multiple-bases belief-propagation for decoding of short block codes [ieeexplore]
Proc. IEEE Symp. on Inform. Theory, Nice, France, pp. 311-315, June 2007.
T.R. Halford
The extraction and complexity limits of graphical modesl for linear codes
PhD thesis, University of Southern California, Los Angeles, CA, USA, May 2007
2006
T.R. Halford and K.M. Chugg
Random redundant iterative soft-in soft-out decoding of linear block codes [ieeexplore]
Proc. IEEE Symp. on Inform. Theory, Seattle, WA, USA, pp. 2230-2234, July 2006.
J. Jiang and K.R. Narayanan
Iterative soft decision decoding of Reed-Solomon codes based on adaptive parity-check matrices [ieeexplore]
IEEE Trans. Inform. Theory, vol. 52, no. 8, pp. 3746-3756, Aug. 2006.
2004
A. Ahmed, R. Koetter, N.R. Shanbhag
Performance analysis of the adaptive parity check matrix based soft-decision decoding algorithm [ieeexplore]
Proc. 38th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, USA, pp. 1995-1999, Nov. 7-10, 2004.
J. Jiang and K.R. Narayanan
Iterative soft decision decoding of Reed Solomon codes based on adaptive parity check matrices [ieeexplore]
Proc. IEEE Symp. on Inform. Theory, Chicago, IL, USA, p. 616, Jun./Jul. 2004.
J. Jiang and K.R. Narayanan
Iterative soft decoding of Reed-Solomon codes [ieeexplore]
IEEE Comm. Letters, vol. 8, no. 4, pp. 244-246, Apr. 2004.
1999
E. Fishler, O. Amrani, Y. Be'ery
Geometrical and performance analysis of GMD and Chase decoding algorithms [ieeexplore]
IEEE Trans. Inf. Theory, vol. 45, no. 5, pp. 1406-1422, Jul. 1999.
1998
M. Breitbach, M. Bossert, R. Lucas, C. Kempter
Letter soft-decision decoding of linear block codes as optimization problem [interscience]
Europ. Trans. on Telecomm., vol. 9, no. 3, pp. 229-315, May-June 1998.
O. Amrani and Y. Be'ery
Bounded-distance decoding: algorithms, decision regions, and pseudo nearest neighbors [ieeexplore]
IEEE Trans. Inf. Theory, vol. 44, no. 7, pp. 3072-3082, Nov. 1998.
Papers on Message-Passing-Based / Linear-Programming-Based Combinatorial Optimization
[UNDER CONSTRUCTION]Last Modified: Tuesday, 15-Sep-2009 02:36:21 PDT