The present invention relates to a decoding apparatus and method, a program storage medium, and a program, which allow high-performance decoding of a modulation code encoded in accordance with a variable-length table. A 17PP-SISO decoder 181 performs SISO decoding on a signal supplied from a PR-SISO decoder 81 by using a Viterbi decoding algorithm or a BCJR decoding algorithm in accordance with a trellis represented by paths corresponding, in a one-to-one fashion, to overall transitions in an entire encoding process in accordance with an encoding table 201 of a 17PP code. A resultant SISO-decoded signal is supplied to a turbo decoder 84 via a deinterleaver 83. The turbo decoder 84 performs turbo decoding on the signal output from the 17PP-SISO decoder 181. The present invention can be applied to a recording/reproducing apparatus for recording/reproducing a signal on/from a storage medium such as a high-density optical disk.