An apparatus for encoding a speech signal by determining a codebook vector of a speech coding algorithm, wherein the apparatus comprises: 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, wherein the apparatus is configured to determine a plurality of linear predictive coefficients depending on the speech signal, wherein the apparatus is configured to determine a residual signal depending on the plurality of linear predictive coefficients, wherein the matrix determiner is configured to determine the autocorrelation matrix R depending on the residual signal, wherein the matrix determiner is configured to determine the autocorrelation matrix R by determining vector coefficients of a vector r, wherein the autocorrelation matrix R comprises 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, characterized in that the codebook vector determiner is configured to determine that codebook vector ê of the speech coding algorithm which maximizes the normalized correlation f e ^ = e T R e ^ 2 e ^ T R e ^ wherein R is the autocorrelation matrix, and wherein ê is one of the codebook vectors of the speech coding algorithm, and wherein e is an original, unquantized residual signal. 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, wherein the apparatus is configured to determine a plurality of linear predictive coefficients depending on the speech signal, wherein the apparatus is configured to determine a residual signal depending on the plurality of linear predictive coefficients, wherein the matrix determiner is configured to determine the autocorrelation matrix R depending on the residual signal, wherein the matrix determiner is configured to determine the autocorrelation matrix R by determining vector coefficients of a vector r, wherein the autocorrelation matrix R comprises 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, characterized in that the codebook vector determiner is configured to determine that codebook vector ê of the speech coding algorithm which maximizes the normalized correlation f e ^ = e T R e ^ 2 e ^ T R e ^ wherein R is the autocorrelation matrix, and wherein ê is one of the codebook vectors of the speech coding algorithm, and wherein e is an original, unquantized residual signal.