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)

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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 languageEnglish
    Title of host publicationApplied Algebra, Algebraic Algorithms, and Error-Correcting Codes : Springer Lecture Notes in Computer Science
    Number of pages10
    Volume5527
    Place of PublicationBerlin
    PublisherSpringer
    Publication date2009
    Pages53-65
    Publication statusPublished - 2009
    Event18th International Symposium AAECC-18 - Tarragona, Spain
    Duration: 1 Jan 2009 → …

    Conference

    Conference18th International Symposium AAECC-18
    CityTarragona, Spain
    Period01/01/2009 → …

    Fingerprint Dive into the research topics of 'Optimal Bipartitet Ramanujan Graphs from Balanced Incomplete Block Designs: Their Characterization and Applications to Expander/LDPC Codes.'. Together they form a unique fingerprint.

    Cite this