A BDD-based approach to constructing LFSRs for parallel CRC encoding
2012 (English)In: Proceedings, IEEE 42nd International Symposium on Multiple-Valued Logic. ISMVL 2012, IEEE Computer Society, 2012, 128-133 p.Conference paper (Refereed)
Cyclic Redundancy Check codes (CRC) are widely used in data communication and storage devices for detecting burst errors. In applications requiring high-speed data transmission, multiple bits of an CRC are computed in parallel. Traditional methods for constructing an Linear Feedback Shift Register (LFSR) generating k bits of an CRC in parallel are based on computing kth power of the connection matrix of the LFSR. We propose an alternative method which is based on computing kth power of the transition relation of the LFSR. We use Binary Decision Diagrams (BDDs) for representing the transition relation and we keep the transition relation partitioned. This allows us to bound the size of BDDs by O(n(2)), where n is the size of the LFSR. Our experimental results show that the presented algorithm asymptotically improves the complexity of previous approaches.
Place, publisher, year, edition, pages
IEEE Computer Society, 2012. 128-133 p.
, International Symposium on Multiple-Valued Logic. Proceedings, ISSN 0195-623X
BDD, LFSR, parallel CRC
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-87201DOI: 10.1109/ISMVL.2012.20ISI: 000309229100023ScopusID: 2-s2.0-84864223710ISBN: 978-076954673-5OAI: oai:DiVA.org:kth-87201DiVA: diva2:501491
42nd IEEE International Symposium on Multiple-Valued Logic, ISMVL 2012; Victoria, BC; 14 May 2012 through 16 May 2012
QC 201209042012-02-142012-02-142012-11-14Bibliographically approved