Optimal Bipartitet Ramanujan Graphs from Balanced Incomplete Block Designs: Their Characterization and Applications to Expander/LDPC Codes.

Tom Høholdt; Heeralal Janwa

Optimal Bipartitet Ramanujan Graphs from Balanced Incomplete Block Designs: Their Characterization and Applications to Expander/LDPC Codes.

Tom Høholdt (Invited author), Heeralal Janwa (Invited author)

University of Puerto Rico

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

We characterize optimaal bipartitet expander graphs and give nessecary and sufficient conditions for optimality. We determine the expansion parameters of the BIBD graphs and show that they yield optimal expander graphs and also bipartitet Ramanujan graphs. in particular, we show that the bipartite graphs derived from finite projective and affine geometries yield optimal Ramanujan graphs. This in turn leads to a theoretical explanation of the good performance of a class of LDPC codes.

Original language	English
Title of host publication	Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes : Springer Lecture Notes in Computer Science
Number of pages	10
Volume	5527
Place of Publication	Berlin
Publisher	Springer
Publication date	2009
Pages	53-65
Publication status	Published - 2009
Event	18th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - Tarragona, Spain Duration: 8 Jun 2009 → 12 Jun 2009 Conference number: 18 http://crises-deim.urv.cat/aaecc/

Conference

Conference	18th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes
Number	18
Country/Territory	Spain
City	Tarragona
Period	08/06/2009 → 12/06/2009
Internet address	http://crises-deim.urv.cat/aaecc/

OpenUrl availability

Full text

Cite this

@inproceedings{b920c20b77dc42fb8a466a9727a16595,

title = "Optimal Bipartitet Ramanujan Graphs from Balanced Incomplete Block Designs: Their Characterization and Applications to Expander/LDPC Codes.",

abstract = "We characterize optimaal bipartitet expander graphs and give nessecary and sufficient conditions for optimality. We determine the expansion parameters of the BIBD graphs and show that they yield optimal expander graphs and also bipartitet Ramanujan graphs. in particular, we show that the bipartite graphs derived from finite projective and affine geometries yield optimal Ramanujan graphs. This in turn leads to a theoretical explanation of the good performance of a class of LDPC codes.",

author = "Tom H{\o}holdt and Heeralal Janwa",

year = "2009",

language = "English",

volume = "5527",

pages = "53--65",

booktitle = "Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes",

publisher = "Springer",

note = "18th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-18 ; Conference date: 08-06-2009 Through 12-06-2009",

url = "http://crises-deim.urv.cat/aaecc/",

}

Høholdt, T & Janwa, H 2009, Optimal Bipartitet Ramanujan Graphs from Balanced Incomplete Block Designs: Their Characterization and Applications to Expander/LDPC Codes. in Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes: Springer Lecture Notes in Computer Science. vol. 5527, Springer, Berlin, pp. 53-65, 18th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Tarragona, Spain, 08/06/2009.

Optimal Bipartitet Ramanujan Graphs from Balanced Incomplete Block Designs: Their Characterization and Applications to Expander/LDPC Codes. / Høholdt, Tom (Invited author); Janwa, Heeralal (Invited author).
Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes: Springer Lecture Notes in Computer Science. Vol. 5527 Berlin: Springer, 2009. p. 53-65.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Optimal Bipartitet Ramanujan Graphs from Balanced Incomplete Block Designs: Their Characterization and Applications to Expander/LDPC Codes.

AU - Høholdt, Tom

AU - Janwa, Heeralal

N1 - Conference code: 18

PY - 2009

Y1 - 2009

N2 - We characterize optimaal bipartitet expander graphs and give nessecary and sufficient conditions for optimality. We determine the expansion parameters of the BIBD graphs and show that they yield optimal expander graphs and also bipartitet Ramanujan graphs. in particular, we show that the bipartite graphs derived from finite projective and affine geometries yield optimal Ramanujan graphs. This in turn leads to a theoretical explanation of the good performance of a class of LDPC codes.

AB - We characterize optimaal bipartitet expander graphs and give nessecary and sufficient conditions for optimality. We determine the expansion parameters of the BIBD graphs and show that they yield optimal expander graphs and also bipartitet Ramanujan graphs. in particular, we show that the bipartite graphs derived from finite projective and affine geometries yield optimal Ramanujan graphs. This in turn leads to a theoretical explanation of the good performance of a class of LDPC codes.

M3 - Article in proceedings

VL - 5527

SP - 53

EP - 65

BT - Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes

PB - Springer

CY - Berlin

T2 - 18th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes

Y2 - 8 June 2009 through 12 June 2009

ER -

Optimal Bipartitet Ramanujan Graphs from Balanced Incomplete Block Designs: Their Characterization and Applications to Expander/LDPC Codes.

Abstract

Conference

OpenUrl availability

Fingerprint

Cite this