1. An encoding device comprising: a first band dividing unit operable to divide an input signal into a low frequency signal representing a signal in a lower frequency band and a high frequency signal representing a signal in a higher frequency band; a lower frequency band encoding unit operable to encode the divided low frequency signal and generate a low frequency code; a similarity judging unit operable to judge similarity between the high frequency signal and the low frequency signal; a plurality of higher frequency band encoding units operable to encode the high frequency signal through respective encoding methods and generate a high frequency code; an encoding selecting unit operable to select one of a plurality of the higher frequency band encoding units, have the selected higher frequency band encoding unit perform encoding, and generate selection information specifying an encoding method employed by the selected higher frequency band encoding unit; and a code multiplexing unit operable to multiplex the low frequency code from the lower frequency band encoding unit, the high frequency code from the selected higher frequency band encoding unit and the selection information from the encoding selecting unit, and generate an output code.