Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A BDD-based approach to constructing LFSRs for parallel CRC encoding
KTH, School of Information and Communication Technology (ICT), Electronic Systems.ORCID iD: 0000-0001-7382-9408
KTH, School of Information and Communication Technology (ICT), Electronic Systems.
2012 (English)In: Proceedings, IEEE 42nd International Symposium on Multiple-Valued Logic. ISMVL 2012, IEEE Computer Society, 2012, 128-133 p.Conference paper, Published paper (Refereed)
Abstract [en]

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.
Series
International Symposium on Multiple-Valued Logic. Proceedings, ISSN 0195-623X
Keyword [en]
BDD, LFSR, parallel CRC
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-87201DOI: 10.1109/ISMVL.2012.20ISI: 000309229100023Scopus ID: 2-s2.0-84864223710ISBN: 978-076954673-5 (print)OAI: oai:DiVA.org:kth-87201DiVA: diva2:501491
Conference
42nd IEEE International Symposium on Multiple-Valued Logic, ISMVL 2012; Victoria, BC; 14 May 2012 through 16 May 2012
Note

QC 20120904

Available from: 2012-02-14 Created: 2012-02-14 Last updated: 2012-11-14Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Dubrova, Elena

Search in DiVA

By author/editor
Dubrova, ElenaSarif Mansouri, Shohreh
By organisation
Electronic Systems
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 78 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf