use Encode;

my $enc = Encode::find_encoding('utf-8'); # or some other encoding...
my %encoded = map {
      $enc->encode($_), $enc->encode( $decoded{$_} )
  } keys %decoded;