Convolutionally encoding a data stream includes inputting a first block of two or more bits in parallel into a shift register. A number of intermediate calculations are performed in parallel using a number of respective delayed shift register outputs; and said number of intermediate calculations are output to form a convolutionally encoded sequence.In one example, a register (of individual bits stored in words), is set up. The register is longer than the constraint length means that a relatively large number of input bits can be read from memory only once, thus avoiding many independent moves of operands to and from memory. Since the register is longer than the constraint length, the register need only be shifted once for every `a+1` input bits, rather than once for each bit.