M.Sc Thesis

M.Sc StudentAssaf Uri
SubjectAspects in Soft Decision Decoding of Reed-Solomon
DepartmentDepartment of Electrical and Computer Engineering
Supervisor DR. Shraga Bross


Finding efficient soft-decision decoding is a fertile field of research. Some of the soft decision algorithms are of special interest :

- Kaneko algorithm is an efficient maximum-likelihood decoding algorithm for linear block codes, which is based on any algebraic decoder. Like Chase algorithm, it generates candidate codewords.

- Koetter-Vardy (K-V) algorithm is a soft decision algebraic list decoder. K-V algorithm utilizes the parameter cost which sets the algorithm’s complexity and performance.

- Turbo Product Codes received some attention in recent papers, and were applied mainly for binary codes and binary signaling.

Main results and conclusions

Kaneko Algorithm

- If utilized for decoding low-rate codes, The performance of Kaneko algorithm greatly depends on the practical limit of test patterns. Therefore, for complexity reasons,  Kaneko algorithm is relevant mainly for high-rate codes.

- We propose a sub-optimal symbol reliability which utilizes a predetermined parameter instead of the noise variance, with minimal impairment to the decoder’s performance.

-  In order to avoid useless decoding iterations, we suggest to maintain a storage of all the decoded codewords. We discuss the complexity of such procedure and the situations at which it may be beneficial.

Koetter-Vardy Algorithm

- The complexity of K-V algorithm is found to be O(cost3). Since the complexity is independent of the code rate, K-V algorithm is attractive mainly for low-rate codes.

- We prove a surprising flaw in K-V algorithm, i.e. at low SNR and high-rate codes K-V algorithm may fail to output the transmitted codeword even if there are no errors in the received codeword at all.

- We discuss choice of decoding parameters, mainly cost. The lack of monotony with respect to cost is discussed. 

Turbo Product Codes

- Turbo product codes decoding algorithm is adjusted for RS codes and MPSK signaling.

- Turbo product code (TPC) with RS code as component codes and MPSK modulation outperforms standard Kaneko algorithm with similar code rate and complexity with only two full iterations.