A trellis encoder for trellis encoding a dual transmission stream. A first multiplexer selectively outputs one of a predetermined first bit of the dual transmission stream and a value stored in a first memory according to an external control signal. A first adder adds the value output from the first multiplexer to the value stored in the first memory, outputs the added value, and stores the added value in the first memory. A second multiplexer selectively outputs one of a predetermined second bit of the dual transmission stream and a value stored in a second memory according to the external control signal. A second adder adds the value output from the second multiplexer to the value stored in the second memory and stores the added value in a third memory. Thus, an initialization is effectively performed before trellis encoding is performed.