A method for encoding includes receiving input data symbols to be encoded with an Error Correction Code (ECC) so as to produce a code word of the ECC including redundancy symbols. The input data symbols are applied first and second processing stages, such that the first processing stage performs a first polynomial division by a fixed-coefficient polynomial with a first degree of parallelism, and the second processing stage performs a second polynomial division by a configurable-coefficient polynomial with a second degree of parallelism that is smaller than the first degree of parallelism, so as to jointly produce the redundancy symbols.