A decoder includes variable-node circuitry, check-node circuitry and a Message Passing (MP) module, which includes multiple configurable partial cyclic shifters that each supports only a partial subset of shift values out of a full range of shift values 0 . . . L−1. The variable-node circuitry and check-node circuitry are configured to exchange messages with one another in accordance with a parity check matrix that represents a respective Quasi-Cyclic (QC)-Low Density Parity Check (LDPC) Error Correcting Code (ECC) and that includes L-by-L sub-matrices, and to process the exchanged messages to decode a given code word that was encoded using the QC-LDPC ECC. The MP module is configured to schedule the variable-node circuitry and check-node circuitry that are interconnected in accordance with a respective sub-matrix to exchange L messages simultaneously by assigning a given partial cyclic shifter to shift the L messages cyclically a number of positions that depends on a structure of the respective sub-matrix.