audio coding and decoding apparatuses and methods that can optimize the quality of an audio signal including harmonics , and recording mediums storing the methods . an audio coding apparatus includes : a first harmonic coding module performing first harmonic coding on an input audio signal using a pitch lag of the input audio signal and producing a quantized linear prediction coding coefficient ; a first detector detecting a first difference audio signal from a difference between an audio signal output from the first harmonic coding module and the input audio signal ; a second harmonic coding module performing harmonic coding on the first difference audio signal using the quantized linear prediction coding coefficient and a previous harmonic coding result ; a second detector detecting a second difference audio signal obtained from a difference between an audio signal output from the second harmonic coding module and the first difference audio signal ; and a code excited linear prediction module celp coding the second difference audio signal using the quantized linear prediction coding coefficient obtained from the first harmonic coding module .