Vector　quantization　(VQ)　is　an　effective　means　of　data　compression　for　it　maps　a　set　of　real　numbers　into　a　single　integer.　A　novel　scheme　for　VQ　codebook　generation,　namely　the　balance　evolution　(BE)　algorithm,　is　presented.　The　proposed　scheme　decomposes　an　initial　codebook　into　several　sub-sets　of　closely　located　codevectors　and　then　designs　each　sub-codebook　using　the　generalized　Lloyd　algorithm　(GLA)　based　on　a　carefully　chosen　cluster　of　signal　vectors　inside　the　training　set.　It　reduces　the　variance　in　contributions　of　different　sub-codebooks　to　the　coding　performance　by　adapting　the　composition　of　each　training　sub-set.　Convergence　of　the　proposed　procedure　is　ensured　via　decreasing　the　total　number　of　sub-codebooks　gradually　to　one.　Experiments　show　that　the　BE　algorithm　outperforms　the　Linde,　Buzo,　Gray　(1980)　algorithm　and　GLA.　However,　the　achievement　is　accompanied　by　an　increase　in　off-line　computational　complexity.　©　2002　IEEE.