Fast Erasure Decoding of Reed-Solomon Codes Based on Decomposition of Vandermonde Matrix

Zebing Lin; Jingjie Lv; Pingping Li; Linqi Song; Hui Liang; Hanxu Hou

doi:10.1109/WCSP62071.2024.10827202

Fast Erasure Decoding of Reed-Solomon Codes Based on Decomposition of Vandermonde Matrix

Zebing Lin, Jingjie Lv, Pingping Li, Linqi Song, Hui Liang, Hanxu Hou^*

^*Corresponding author for this work

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

Abstract

Reed-Solomon (RS) codes are widely applied in storage systems. The main bottleneck of RS codes is that the high decoding complexity defined as the number of multiplications and additions. In this paper, we propose a fast decoding algorithm for RS codes that requires fewer number of multiplications. Our fast decoding algorithm is designed by a decomposition of Vandermonde matrices. We show that our decoding algorithm requires fewer number of multiplications than the existing best known algorithm when the number of parities T is large. When the codeword length N = 16, our decoding algorithm reduces the number of multiplications by 7% and 29% when T = 4 and T = 7, respectively, compared with the best known decoding algorithm. © 2024 IEEE.

Original language	English
Title of host publication	The Sixteenth International Conference on Wireless Communications and Signal Processing (WCSP 2024)
Publisher	IEEE
Pages	96-101
ISBN (Electronic)	9798350390643
ISBN (Print)	9798350390650
DOIs	https://doi.org/10.1109/WCSP62071.2024.10827202
Publication status	Published - Oct 2024
Event	16th International Conference on Wireless Communications and Signal Processing (WCSP 2024): Charging up wireless communications and signal processing with intelligence - Hefei, China Duration: 24 Oct 2024 → 26 Oct 2024 http://www.ic-wcsp.org/2024/

Publication series

Name	International Conference on Wireless Communications and Signal Processing, WCSP

Conference

Conference	16th International Conference on Wireless Communications and Signal Processing (WCSP 2024)
Abbreviated title	WCSP2024
Place	China
City	Hefei
Period	24/10/24 → 26/10/24
Internet address	http://www.ic-wcsp.org/2024/

Funding

This work was partially supported by Key Area Research and Development Program of Guangdong Province under grant No. 2020B0101110003, the National Natural Science Foundation of China (No. 62071121, 62371411, 12025104) and the Research Grants Council of the Hong Kong SAR under Grant GRF 11217823 and Collaborative Research Fund C1042-23GF, InnoHK initiative, the Government of the HKSAR, Laboratory for AI-Powered Financial Technologies.

Research Keywords

decomposition of Vandermonde matrices
erasure decoding
Reed-Solomon codes

RGC Funding Information

RGC-funded

Access Output

10.1109/WCSP62071.2024.10827202

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Lin, Z., Lv, J., Li, P., Song, L., Liang, H., & Hou, H. (2024). Fast Erasure Decoding of Reed-Solomon Codes Based on Decomposition of Vandermonde Matrix. In The Sixteenth International Conference on Wireless Communications and Signal Processing (WCSP 2024) (pp. 96-101). (International Conference on Wireless Communications and Signal Processing, WCSP). IEEE. https://doi.org/10.1109/WCSP62071.2024.10827202

@inproceedings{008881332ac747cf8962393c58818c0b,

title = "Fast Erasure Decoding of Reed-Solomon Codes Based on Decomposition of Vandermonde Matrix",

abstract = "Reed-Solomon (RS) codes are widely applied in storage systems. The main bottleneck of RS codes is that the high decoding complexity defined as the number of multiplications and additions. In this paper, we propose a fast decoding algorithm for RS codes that requires fewer number of multiplications. Our fast decoding algorithm is designed by a decomposition of Vandermonde matrices. We show that our decoding algorithm requires fewer number of multiplications than the existing best known algorithm when the number of parities T is large. When the codeword length N = 16, our decoding algorithm reduces the number of multiplications by 7% and 29% when T = 4 and T = 7, respectively, compared with the best known decoding algorithm. {\textcopyright} 2024 IEEE.",

keywords = "decomposition of Vandermonde matrices, erasure decoding, Reed-Solomon codes",

author = "Zebing Lin and Jingjie Lv and Pingping Li and Linqi Song and Hui Liang and Hanxu Hou",

year = "2024",

month = oct,

doi = "10.1109/WCSP62071.2024.10827202",

language = "English",

isbn = "9798350390650",

series = "International Conference on Wireless Communications and Signal Processing, WCSP",

publisher = "IEEE",

pages = "96--101",

booktitle = "The Sixteenth International Conference on Wireless Communications and Signal Processing (WCSP 2024)",

address = "United States",

note = "16th International Conference on Wireless Communications and Signal Processing (WCSP 2024) : Charging up wireless communications and signal processing with intelligence, WCSP2024 ; Conference date: 24-10-2024 Through 26-10-2024",

url = "http://www.ic-wcsp.org/2024/",

}

Lin, Z, Lv, J, Li, P, Song, L, Liang, H & Hou, H 2024, Fast Erasure Decoding of Reed-Solomon Codes Based on Decomposition of Vandermonde Matrix. in The Sixteenth International Conference on Wireless Communications and Signal Processing (WCSP 2024). International Conference on Wireless Communications and Signal Processing, WCSP, IEEE, pp. 96-101, 16th International Conference on Wireless Communications and Signal Processing (WCSP 2024), Hefei, China, 24/10/24. https://doi.org/10.1109/WCSP62071.2024.10827202

Fast Erasure Decoding of Reed-Solomon Codes Based on Decomposition of Vandermonde Matrix. / Lin, Zebing; Lv, Jingjie; Li, Pingping et al.
The Sixteenth International Conference on Wireless Communications and Signal Processing (WCSP 2024). IEEE, 2024. p. 96-101 (International Conference on Wireless Communications and Signal Processing, WCSP).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Fast Erasure Decoding of Reed-Solomon Codes Based on Decomposition of Vandermonde Matrix

AU - Lin, Zebing

AU - Lv, Jingjie

AU - Li, Pingping

AU - Song, Linqi

AU - Liang, Hui

AU - Hou, Hanxu

PY - 2024/10

Y1 - 2024/10

N2 - Reed-Solomon (RS) codes are widely applied in storage systems. The main bottleneck of RS codes is that the high decoding complexity defined as the number of multiplications and additions. In this paper, we propose a fast decoding algorithm for RS codes that requires fewer number of multiplications. Our fast decoding algorithm is designed by a decomposition of Vandermonde matrices. We show that our decoding algorithm requires fewer number of multiplications than the existing best known algorithm when the number of parities T is large. When the codeword length N = 16, our decoding algorithm reduces the number of multiplications by 7% and 29% when T = 4 and T = 7, respectively, compared with the best known decoding algorithm. © 2024 IEEE.

AB - Reed-Solomon (RS) codes are widely applied in storage systems. The main bottleneck of RS codes is that the high decoding complexity defined as the number of multiplications and additions. In this paper, we propose a fast decoding algorithm for RS codes that requires fewer number of multiplications. Our fast decoding algorithm is designed by a decomposition of Vandermonde matrices. We show that our decoding algorithm requires fewer number of multiplications than the existing best known algorithm when the number of parities T is large. When the codeword length N = 16, our decoding algorithm reduces the number of multiplications by 7% and 29% when T = 4 and T = 7, respectively, compared with the best known decoding algorithm. © 2024 IEEE.

KW - decomposition of Vandermonde matrices

KW - erasure decoding

KW - Reed-Solomon codes

UR - http://www.scopus.com/inward/record.url?scp=85217577893&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85217577893&origin=recordpage

U2 - 10.1109/WCSP62071.2024.10827202

DO - 10.1109/WCSP62071.2024.10827202

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9798350390650

T3 - International Conference on Wireless Communications and Signal Processing, WCSP

SP - 96

EP - 101

BT - The Sixteenth International Conference on Wireless Communications and Signal Processing (WCSP 2024)

PB - IEEE

T2 - 16th International Conference on Wireless Communications and Signal Processing (WCSP 2024)

Y2 - 24 October 2024 through 26 October 2024

ER -

Lin Z, Lv J, Li P, Song L, Liang H, Hou H. Fast Erasure Decoding of Reed-Solomon Codes Based on Decomposition of Vandermonde Matrix. In The Sixteenth International Conference on Wireless Communications and Signal Processing (WCSP 2024). IEEE. 2024. p. 96-101. (International Conference on Wireless Communications and Signal Processing, WCSP). doi: 10.1109/WCSP62071.2024.10827202

Fast Erasure Decoding of Reed-Solomon Codes Based on Decomposition of Vandermonde Matrix

Abstract

Publication series

Conference

Funding

Research Keywords

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

GRF: Towards Building An Adaptive Distributed Computation Framework for Massive Context Interplay

Cite this

Fast Erasure Decoding of Reed-Solomon Codes Based on Decomposition of Vandermonde Matrix

Abstract

Publication series

Conference

Funding

Research Keywords

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Projects

GRF: Towards Building An Adaptive Distributed Computation Framework for Massive Context Interplay

Cite this