Unified parallel encoding and decoding algorithms for Dandelion-like codes

作者：Caminiti Saverio^*; Petreschi Rossella

来源：Journal of Parallel and Distributed Computing, 2010, 70(11): 1119-1127.

DOI：10.1016/j.jpdc.2010.07.003

• Bijective tree encoding
• Prufer code
• Dandelion-like codes
• PRAM algorithms

The Dandelion-like codes are eight bijections between labeled trees and strings of node labels. The literature contains optimal sequential algorithms for these bijections, but no parallel algorithms have been reported. In this paper the first parallel encoding and decoding algorithms for Dandelion-like codes are presented. Namely, a unique encoding algorithm and a unique decoding algorithm, which when properly parameterized, can be used for all Dandelion-like codes, are designed. These algorithms are optimal in the sequential setting. The encoding algorithm implementation on an EREW PRAM is optimal, while the efficient implementation of the decoding algorithm requires concurrent reading.

• 出版日期2010-11