In order to encode an original sequence of binary data (u), a first padding operation (508) is performed, supplementing the original sequence (u) so that the supplemented sequence (u) is divisible by a first divisor polynomial; a first recursive convolutional encoding operation (508) is performed, using the first divisor polynomial, encoding the supplemented original sequence (u); an interleaving operation (506) is performed, permuting the binary data in the original sequence (u) by means of a specific permutation, so as to obtain an interleaved sequence (u*); a second padding operation (510) is performed, supplementing the interleaved sequence (u*) so that the supplemented interleaved sequence (u*) is divisible by a second divisor polynomial (g2); and a second recursive convolutional encoding operation (510) is performed, using the second divisor polynomial, encoding the supplemented interleaved sequence (u*).