This is an open access article published by the IET under the Creative Commons Attribution-NonCommercial-NoDerivs License (http://creativecommons.org/licenses/by-nc-nd/3.0/)
In this paper, the author presents an optimised parallel implementation of a flexible maximum a-posteriori decoder for synchronisation error correcting codes, supporting a very wide range of code sizes and channel conditions. On mid-range GPUs the author demonstrates decoding speedups of more than two orders of magnitude over a central processing unit implementation of the same optimised algorithm, and more than an order of magnitude over the author's earlier GPU implementation. The prominent challenge is to maintain high parallelisation efficiency over a wide range of code sizes and channel conditions, and different execution hardware. The author ensures this with a dynamic strategy for choosing parallel execution parameters at run-time. They also present a variant that trades off some decoding speed for significantly reduced memory requirement, with no loss to the decoder's error correction performance. The increased throughput of their implementation and its ability to work with less memory allow us to analyse larger codes and poorer channel conditions, and makes practical use of such codes more feasible.
References
-
-
1)
-
4. Coumou, D.J., Sharma, G.: ‘Insertion, deletion codes with feature-based embedding: a new paradigm for watermark synchronization with applications to speech watermarking’, IEEE Trans. Inf. Forensics Sec., 2008, 3, (2), pp. 153–165 (doi: 10.1109/TIFS.2008.920728).
-
2)
-
13. Wu, M., Sun, Y., Wang, G., Cavallaro, J.: ‘Implementation of a high throughput 3GPP turbo decoder on GPU’, J. Signal Process. Syst., 2011, 65, (2), pp. 171–183 (doi: 10.1007/s11265-011-0617-7).
-
3)
-
1. Mercier, H., Bhargava, V., Tarokh, V.: ‘A survey of error-correcting codes for channels with symbol synchronization errors’, IEEE Commun. Surv. Tutor., 2010, 12, (1), pp. 87–96, (doi: 10.1109/SURV.2010.020110.00079).
-
4)
-
15. Davey, M.C., MacKay, D.J.C.: ‘Reliable communication over channels with insertions, deletions, and substitutions’, IEEE Trans. Inf. Theory, 2001, 47, (2), pp. 687–698 (doi: 10.1109/18.910582).
-
5)
-
2. Hu, J., Duman, T., Erden, M., Kavcic, A.: ‘Achievable information rates for channels with insertions, deletions, and intersymbol interference with i.i.d. inputs’, IEEE Trans. Commun., 2010, 58, (4), pp. 1102–1111 (doi: 10.1109/TCOMM.2010.04.080683).
-
6)
-
9. Briffa, J.A.: ‘A GPU implementation of a MAP decoder for synchronization error correcting codes’, IEEE Commun. Lett., 2013, 17, (5), pp. 996–999 (doi: 10.1109/LCOMM.2013.031913.130203).
-
7)
-
3. Hu, J., Duman, T., Kurtas, E., Erden, M.: ‘Bit-patterned media with written-in errors: modeling, detection, and theoretical limits’, IEEE Trans. Magn., 2007, 43, (8), pp. 3517–3524 (doi: 10.1109/TMAG.2007.898307).
-
8)
-
15. Bahl, L.R., Jelinek, F.: ‘Decoding for channels with insertions, deletions, and substitutions with applications to speech recognition’, IEEE Trans. Inf. Theory, 1975, 21, (4), pp. 404–411 (doi: 10.1109/TIT.1975.1055419).
-
9)
-
5. Bardyn, D., Briffa, J.A., Dooms, A., Schelkens, P.: ‘Forensic data hiding optimized for JPEG 2000’. Proc. IEEE Int. Symp. Circuits and Systems, Rio de Janeiro, Brazil, 15–18 May 2011.
-
10)
-
17. Bahl, L.R., Jelinek, F.: ‘Decoding for channels with insertions, deletions, and substitutions with applications to speech recognition’, IEEE Trans. Inf. Theory, 1975, 21, (4), pp. 404–411 (doi: 10.1109/TIT.1975.1055419).
-
11)
-
12)
-
3. Hu, J., Duman, T., Kurtas, E., Erden, M.: ‘Bit-patterned media with written-in errors: modeling, detection, and theoretical limits’, IEEE Trans. Magn., 2007, 43, (8), pp. 3517–3524 (doi: 10.1109/TMAG.2007.898307).
-
13)
-
16. Ratzer, E.A.: ‘Marker codes for channels with insertions and deletions’, Ann. Telecommun., 2005, 60, pp. 29–44.
-
14)
-
8. Buttigieg, V., Briffa, J.A.: ‘Codebook and marker sequence design for synchronization-correcting codes’. Proc. IEEE Int. Symp. Information Theory, St. Petersburg, Russia, 31 July–5 August 2011.
-
15)
-
16)
-
2. Hu, J., Duman, T., Erden, M., Kavcic, A.: ‘Achievable information rates for channels with insertions, deletions, and intersymbol interference with i.i.d. inputs’, IEEE Trans. Commun., 2010, 58, (4), pp. 1102–1111 (doi: 10.1109/TCOMM.2010.04.080683).
-
17)
-
18. Granlund, T.: ‘GNU MP: the GNU multiple precision arithmetic library’, .
-
18)
-
M.C. Davey ,
D.J.C. Mackay
.
Reliable communications over channels with insertions, deletions and substitutions.
IEEE Trans. Inf. Theory
,
2 ,
687 -
698
-
19)
-
4. Coumou, D.J., Sharma, G.: ‘Insertion, deletion codes with feature-based embedding: a new paradigm for watermark synchronization with applications to speech watermarking’, IEEE Trans. Inf. Forensics Sec., 2008, 3, (2), pp. 153–165 (doi: 10.1109/TIFS.2008.920728).
-
20)
-
21. Mercier, H., Bhargava, V.K., Tarokh, V.: ‘A survey of error-correcting codes for channels with symbol synchronization errors’, IEEE Commun. Surveys and Tutorials, 2010, 12, (1), , pp. 87–96 (doi: 10.1109/SURV.2010.020110.00079).
-
21)
-
9. Briffa, J.A.: ‘A GPU implementation of a MAP decoder for synchronization error correcting codes’, IEEE Commun. Lett., 2013, 17, (5), pp. 996–999 (doi: 10.1109/LCOMM.2013.031913.130203).
-
22)
-
11. Briffa, J.A., Buttigieg, V., Wesemeyer, S.: ‘Time-varying block codes for synchronization errors: MAP decoder and practical issues’, .
-
23)
-
7. Briffa, J.A., Schaathun, H.G., Wesemeyer, S.: ‘An improved decoding algorithm for the Davey–MacKay construction’. Proc. IEEE Int. Conf. Communications, Cape Town, South Africa, 23–27 May 2010.
-
24)
-
20. Eckel, B.: ‘Thinking in C++’ (Pearson Education, 2000, 2nd edn.), vol. 1.
-
25)
-
21. Eckel, B., Allison, C.: ‘Thinking in C++’ (Pearson Education, 2003, 2nd edn.), vol. 2.
-
26)
-
17. Briffa, J.A., Schaathun, H.G.: ‘Improvement of the Davey–MacKay construction’. Proc. IEEE Int. Symp. Information Theory and its Applications, Auckland, New Zealand, 7–10 December 2008, pp. 235–238.
-
27)
-
28)
-
14. Xianjun, J., Canfeng, C., Jaaskelainen, P., Guzma, V., Berg, H.: ‘A 122Mb/s turbo decoder using a mid-range GPU’. 2013 Ninth Int. Wireless Communications and Mobile Computing Conf. (IWCMC), 2013, pp. 1090–1094.
-
29)
-
12. Lee, D., Wolf, M., Kim, H.: ‘Design space exploration of the turbo decoding algorithm on GPUs’. Proc. Int. Conf. Compilers, Architectures and Synthesis for Embedded Systems. ACM, 2010, pp. 217–226.
-
30)
-
19. Rennich, S.: ‘CUDA C/C++ streams and concurrency’. GPU Technology Conf. NVIDIA, 2011.
-
31)
-
13. Wu, M., Sun, Y., Wang, G., Cavallaro, J.: ‘Implementation of a high throughput 3GPP turbo decoder on GPU’, J. Signal Process. Syst., 2011, 65, (2), pp. 171–183 (doi: 10.1007/s11265-011-0617-7).
http://iet.metastore.ingenta.com/content/journals/10.1049/joe.2014.0049
Related content
content/journals/10.1049/joe.2014.0049
pub_keyword,iet_inspecKeyword,pub_concept
6
6