On Trellis Structures for Reed–Muller Codes

We study trellises of Reed–Muller codes from first principles. Our approach to local trellis behaviour seems to be new and yields amongst other things another proof of a result of Berger and Beʹery on the state complexity of Reed–Muller codes. We give a general form of a minimal-span generator matrix for the family of Reed–Muller codes with their standard bit-order. We apply this to determining the number of parallel subtrellises in any uniform sectionalisation of a Reed–Muller code and to designing trellises for Reed–Muller codes with more parallel subtrellises than the minimal trellis, but with the same state complexity.