Speech coding means turning voice into digital. I've written much on this subject so be sure to click on the links below if there are points you don't understand . . .
GSM is a digital system, so speech which is inherently analog, has to be digitized. The method employed by ISDN, and by current telephone systems for multiplexing voice lines over high speed trunks and optical fiber lines, is Pulse Coded Modulation (PCM). The output stream from PCM is 64 kbps, too high a rate to be feasible over a radio link. The 64 kbps signal, although simple to implement, contains much redundancy. The GSM group studied several speech coding algorithms on the basis of subjective speech quality and complexity (which is related to cost, processing delay, and power consumption once implemented) before arriving at the choice of a Regular Pulse Excited -- Linear Predictive Coder (RPE--LPC) with a Long Term Predictor loop.
Conventional cellular uses an equally intimidating algorithm named Vector Sum Excited Linear Predictive speech compression. Ugh. Click here to learn about it.
Basically, information from previous samples, which does not change very quickly, is used to predict the current sample. The coefficients of the linear combination of the previous samples, plus an encoded form of the residual, the difference between the predicted and actual sample, represent the signal. Speech is divided into 20 millisecond samples, each of which is encoded as 260 bits, giving a total bit rate of 13 kbps.
This is the subject of digital signal processing. Read about it here.
This is the so-called Full-Rate speech coding. Recently, an Enhanced Full-Rate (EFR) speech coding algorithm has been implemented by some North American GSM1900 operators. This is said to provide improved speech quality using the existing 13 kbps bit rate.
Nokia said in January, 1997 that they would start shipping Enhanced Full Rate voice codecs by March 1997: http://press.nokia.com/PR/199701/775480_5.html; I must assume their use is now wide spread.