This paper proposes a 4 kb/s speech coding method with extremely small computational amount and memory requirements, ULCELP (Ultra small computational amount JLearned CELP). ULCELP is based on the M-LCELP (Multi-mode Learned CELP) method, which was submitted to the North-America TIA halfrate digital cellular telephone standardization contest. In order to drastically reduce the computation and memory requirements, while maintaining good quality synthetic speech at 4 kb/s, the following techniques are developed; (l)Codebooks are changed in accord with voiced and unvoiced segments, (2)Two-stage closed-closed adaptive codebook search with a small computational amount and pitch lag differential coding, (3)A small computational amount and memory requirement excitation codebook search. ULCELP requires less than 3 MOPS of computation amount, and less than 2k word memory (RAM) amount. The MOS subjective evaluation results show that 4 kb/s ULCELP speech quality is close to that of G.726 AD-PCM at 24 kb/s. The result demonstrates that the ULCELP provides sufficient speech quality for voice storage applications.