An apparatus for encoding a speech signal that determines a codebook vector of a speech coding algorithm includes a matrix determiner for determining an autocorrelation matrix R, and a codebook vector determiner for determining the codebook vector depending on the autocorrelation matrix R. The matrix determiner determines the autocorrelation matrix R by determining vector coefficients of a vector r, wherein the autocorrelation matrix R includes a plurality of rows and a plurality of columns, wherein the vector r indicates one of the columns or one of the rows of the autocorrelation matrix R, wherein R(i, j)=r(|i−j|), wherein R(i, j) indicates the coefficients of the autocorrelation matrix R, wherein i is a first index indicating one of a plurality of rows of the autocorrelation matrix R, and wherein j is a second index indicating one of the plurality of columns of the autocorrelation matrix R.