When a voice encoding apparatus embeds any data in encoded voice code, the apparatus determines whether data embedding condition is satisfied using a first element code from among element codes constituting the encoded voice code, and a threshold value. If the data embedding condition is satisfied, the apparatus embeds optional data in the encoded voice code by replacing a second element code with the optional data. When a voice decoding apparatus extracts data that has been embedded in encoded voice code, the apparatus determines whether data embedding condition is satisfied using a first element code from among element codes constituting the encoded voice code, and a threshold value. If the data embedding condition is satisfied, the apparatus determines that optional data has been embedded in the second element code portion of the encoded voice code and extracts this embedded data.