A Parallel Algorithm for Enumerating Joint Weight of a Binary Linear Code in Network Coding

Author

Ando, Shohei ; Ino, Fumihiko ; Fujiwara, Toru ; Hagihara, Kenichi

Author_Institution

Grad. Sch. of Inf. Sci. & Technol., Osaka Univ., Suita, Japan

fYear

2014

Firstpage

137

Lastpage

143

Abstract

In this paper, we present a parallel algorithm for enumerating joint weight of a binary linear (n, k) code, aiming at accelerating assessment of its decoding error probability for network coding. To reduce the number of pairs of code words to be investigated, our parallel algorithm reduces dimension k by focusing on the all-one vector included in many practical codes. We also employ a population count instruction to compute joint weight of code words with a less number of instructions. Our algorithm is implemented on a multi-core CPU system and an NVIDIA GPU system using Open MP and compute unified device architecture (CUDA), respectively. We apply our implementation to a sub code of a (127,22) BCH code to evaluate the impact of acceleration.

Keywords

BCH codes; binary codes; error statistics; graphics processing units; linear codes; parallel algorithms; BCH code; CUDA; NVIDIA GPU system; Open MP; all-one vector; binary linear code; code words; compute unified device architecture; decoding error probability; joint weight enumeration; multicore CPU system; network coding; parallel algorithm; population count instruction; Acceleration; Graphics processing units; Histograms; Instruction sets; Joints; Parallel algorithms; Vectors;

fLanguage

English

Publisher

ieee

Conference_Titel

Computing and Networking (CANDAR), 2014 Second International Symposium on

Type

conf

DOI

10.1109/CANDAR.2014.23

Filename

7052173