Methods and apparatus are provided for trellis-based modulation encoding. A signal is modulation encoded by encoding one or more blocks of the signal using one or more corresponding edges in a trellis, wherein each edge in the trellis has a corresponding bit pattern; selecting a winning path through the trellis based on at least one transition-based run-length constraint; and generating an encoded sequence using edges associated with the winning path. Exemplary trellis pruning techniques are also provided. The winning path through the trellis is selected by minimizing one or more modulation metrics.