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 study, the authors consider time-varying block (TVB) codes, which generalise a number of previous synchronisation error-correcting codes. They also consider various practical issues related to maximum a posteriori (MAP) decoding of these codes. Specifically, they give an expression for the expected distribution of drift between transmitter and receiver because of synchronisation errors. They determine an appropriate choice for state space limits based on the drift probability distribution. In turn, they obtain an expression for the decoder complexity under given channel conditions in terms of the state space limits used. For a given state space, they also give a number of optimisations that reduce the algorithm complexity with no further loss of decoder performance. They also show how the MAP decoder can be used in the absence of known frame boundaries, and demonstrate that an appropriate choice of decoder parameters allows the decoder to approach the performance when frame boundaries are known, at the expense of some increase in complexity. Finally, they express some existing constructions as TVB codes, comparing performance with published results and showing that improved performance is possible by taking advantage of the flexibility of TVB codes.
References
-
-
1)
-
19. Ferrari, G., Chugg, K.M.: ‘Linear programming-based optimization of the distance spectrum of linear block codes’, IEEE Trans. Inf. Theory, 2003, 49, (7), pp. 1794–1800 (doi: 10.1109/TIT.2003.813483).
-
2)
-
6. Wang, F., Fertonani, D., Duman, T.M.: ‘Symbol-level synchronization and LDPC code design for insertion/deletion channels’, IEEE Trans. Commun., 2011, 59, (5), pp. 1287–1297 (doi: 10.1109/TCOMM.2011.030411.100546).
-
3)
-
18. Perez, L.C., Seghers, J., Costello, D.J.Jr.: ‘A distance spectrum interpretation of turbo codes’, IEEE Trans. Inf. Theory, 1996, 42, (6), pp. 1698–1709 (doi: 10.1109/18.556666).
-
4)
-
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).
-
5)
-
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).
-
6)
-
1. Sellers, F.F.: ‘Bit loss and gain correction code’, IRE Trans. Inf. Theory, 1962, IT-8, pp. 35–38 (doi: 10.1109/TIT.1962.1057684).
-
7)
-
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).
-
8)
-
11. Mansour, M.F., Ahmed, H.T.: ‘A turbo coding scheme for channels with synchronization errors’, IEEE Trans. Commun., 2012, 60, (8), pp. 2091–2100 (doi: 10.1109/TCOMM.2012.061112.110304).
-
9)
-
10. Mansour, M.F., Tewfik, A.H.: ‘Convolutional decoding in the presence of synchronization errors’, IEEE J. Sel. Areas Commun., 2010, 28, (2), pp. 218–227 (doi: 10.1109/JSAC.2010.100211).
-
10)
-
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).
-
11)
-
6. Wang, F., Fertonani, D., Duman, T.M.: ‘Symbol-level synchronization and LDPC code design for insertion/deletion channels’, IEEE Trans. Commun., 2011, 59, (5), pp. 1287–1297 (doi: 10.1109/TCOMM.2011.030411.100546).
-
12)
-
15. 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.
-
13)
-
M.C. Davey ,
D.J.C. Mackay
.
Reliable communications over channels with insertions, deletions and substitutions.
IEEE Trans. Inf. Theory
,
2 ,
687 -
698
-
14)
-
8. Schlauweg, M., Profrock, D., Muller, E.: ‘Correction of insertions and deletions in selective watermarking’. IEEE Int. Conf. Signal Image Technology and Internet Based Systems (SITIS), 2008, 30 November–3 December 2008, pp. 277–284.
-
15)
-
L.C. Perez ,
J. Seghers ,
J.D.J. Costello
.
A distance spectrum interpretation of turbo codes.
IEEE Trans. Inf. Theory
,
1698 -
1709
-
16)
-
11. Mansour, M.F., Ahmed, H.T.: ‘A turbo coding scheme for channels with synchronization errors’, IEEE Trans. Commun., 2012, 60, (8), pp. 2091–2100 (doi: 10.1109/TCOMM.2012.061112.110304).
-
17)
-
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).
-
18)
-
19. Ferrari, G., Chugg, K.M.: ‘Linear programming-based optimization of the distance spectrum of linear block codes’, IEEE Trans. Inf. Theory, 2003, 49, (7), pp. 1794–1800 (doi: 10.1109/TIT.2003.813483).
-
19)
-
14. Briffa, J.A., Schaathun, H.G.: ‘Improvement of the Davey–MacKay construction’. Proc. IEEE Int. Symp. Information Theory and its Applications, Auckland, New Zealand, December 7–10, 2008, pp. 235–238.
-
20)
-
5. Ratzer, E.A.: ‘Marker codes for channels with insertions and deletions’, Ann. Telecommun., 2005, 60, pp. 29–44.
-
21)
-
20. Davey, M.C.: ‘Error-correction using low-density parity-check codes’. , University of Cambridge, 1999.
-
22)
-
21. MacKay, D.J.C.: ‘Information theory, inference, and learning algorithms’ (Cambridge University Press, 2003).
-
23)
-
7. Swart, T., Ferreira, H., dos Santos, M.: ‘Using parallel-interconnected Viterbi decoders to correct insertion/deletion errors’. Seventh AFRICON Conf. Africa, September 2004, vol. 1, pp. 341–344.
-
24)
-
9. Mansour, M., Tewfik, A.: ‘Convolutional decoding in the presence of synchronization errors’, IEEE J. Sel. Areas Commun., 2010, 28, (2), pp. 218–227 (doi: 10.1109/JSAC.2010.100211).
-
25)
-
1. Sellers, F.F.: ‘Bit loss and gain correction code’, IRE Trans. Inf. Theory, 1962, IT-8, pp. 35–38 (doi: 10.1109/TIT.1962.1057684).
-
26)
-
13. 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.
-
27)
-
2. Levenshtein, V.I.: ‘Binary codes capable of correcting deletions, insertions and reversals’, Sov. Phys.–Dokl., 1966, 10, (8), pp. 707–710.
-
28)
-
3. Gallager, R.G.: ‘Sequential decoding for binary channels with noise and synchronization errors’. , Massachusetts Institute of Technology Lexington Lincoln Laboratory, 27October1961.
-
29)
-
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).
-
30)
-
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).
http://iet.metastore.ingenta.com/content/journals/10.1049/joe.2014.0062
Related content
content/journals/10.1049/joe.2014.0062
pub_keyword,iet_inspecKeyword,pub_concept
6
6