mpcode.m

ITU-T G.723.1 Speech Coder: Matlab implementation This package implements the speech coder and de

function [MPGridC, MPPosC, MPSignC] = MPCode (Pulseval, MPpar)
% Combined coding of the position codes for the subframes.
%
% The coding is done in two steps. To code the pulse positions, the
% first step gives a combinatoric code for each subframes. These
% subframe pulse position codes are then combined to give 5 values
% for each frame.

% $Id: MPCode.m 1.3 2004/08/03 G.723.1-v2r1a $

% Sign codes, grid code, and combinatoric coding for each subframe
NSubframe = length (Pulseval);
for (i = 1:NSubframe)
  [MPSignC(i), MPGridC(i), MPPC(i)] = MPBinomCode (i, Pulseval(i), MPpar);
end

% Combine the subframe codes into a group of frame codes
MPPosC = MPFrameCode (MPPC, MPpar);

return

%--------------------
function [MPSignC, MPGridC, MPPC] = MPBinomCode (MPMode, Pulseval, MPpar)
% Form the multipulse pulse sign codes, grid codes, and position codes.

MPGridC = Pulseval.GridI - 1;

% Pulse j is in position m(j) and has gain g(j).
% We need to get the positions in order and then
% code the signs of the gains in those positions.
Np = length (Pulseval.m);
[mS, I] = sort (Pulseval.m);

% A minus gives a 1 and a plus gives a 0
% The first pulse is in the most significant position
Signs = (Pulseval.g(I) < 0);
MPSignC = CombineVals (Signs(Np:-1:1), 2);

% Mark the pulse positions on the grid
Grid = MPpar.Grid{MPMode}{Pulseval.GridI};
Grid = sort (Grid);   % Sort the grid
N = Grid(end);        % Number of positions needed
P = zeros (N,1);
P(mS) = 1;
GridP = P(Grid);      % Pulses on the sorted grid

% Combinatoric coding
MPPC = PPCode (GridP, Np, MPpar.nCk);

return

%--------------------
function MPPosC = MPFrameCode (MPPC, MPpar)

% The multipulse positions for each subframe are represented with a
% combinatoric code. For subframes 1 and 3, there are 6 pulses in 30
% positions. For subframes 2 and 4, there are 5 pulses in 30 positions.
% The total number of combinations of positions for the individual
% subframes is then 30 choose 6 or 30 choose 5.
%   N(1) = N(3) = C(30,6) = 593775,
%   N(2) = N(4) = C(30,5) = 142506.
% Coding the pulse positions for each subframe separately would require
% 20 + 18 + 20 + 18 = 76 bits. The number of combinations for all 4
% subframes is 2^72 < N(1) N(2) N(3) N(4) < 2^73. This can be coded with
% 73 bits, representing a saving of 3 bits with respect to separate
% coding. If we examine the possibility of coding pairs, the best we
% can do is 74 bits.
%
% The strategy used in G.723.1 is to express the code values for each
% subframe in modulo notation,
%   c(k) = p(k)M(k) + q(k),
% where q(k) = mod(c(k),M(k) and p(k) = floor(c(k)/M(k)). For k=1 and
% k=3, use M(k)=2^16, and for k=2 and k=4, use M(k)=2^14.
%
% Then for k=1 and k=3, q(k) can be coded with 16 bits and for k=2 and k=4,
% q(k) can be coded with 14 bits. For k=1 and k=3, p(k) takes on values
% in the interval [0,8], while for k=2 and k=4, p(k) takes on values in the
% interval [0,5]. The total number of the combinations of the 4 p(k)'s is
% 9 x 6 x 9 x 6 = 5184 which can be coded with 13 bits. This approach
% achieves the 73 bit total.
%
% The procedure in G.723.1 allocates 90 values (more than the minimum 72)
% to code p(1) and p(2), and the the remainder of the 13 bit code to code
% p(3) and p(4) (which can represent up to 91 values).
%
% The coding procedure is as follows.
% (1) Get q(k) for each subframe.
% (2) Get p(k) for each subframe.
% (3) Form a combined value as [p(4) + 9 p(3) + 90 p(2) + 810 p(1)]. This
%     is the first code word (13 bits)
% (4) The next 4 codewords are the q(k) (16, 14, 16, and 14 bits).

ModV = MPpar.ModV;

% Code the p(k)'s
p = floor (MPPC ./ ModV);
Cp = CombineVals (p(end:-1:1), MPpar.pLev);

% Code the q(k)'s
q = mod (MPPC, ModV);

MPPosC = [Cp q];

return

%--------------------
function C = PPCode (P, Np, nCk)
% Code positions using a combinatoric code (see below)

NGrid = length (P);

m = Np;
C = nCk(NGrid+1, Np+1) - 1;
for (n = NGrid-1:-1:0)
  if (P(NGrid-1-n+1) ~= 0)
    C = C - nCk(n+1,m+1);
    m = m - 1;
    if (m == 0)
      break
    end
  end
end

return

% Combinatorial coding assigns a code. The procedure for doing this
% coding has been reinvented many times, possibly described first in the
% engineering literature by J. P. M. Schalkwijk, "An Algorithm for Source
% Coding", IEEE Trans. Inform. Theory, vol IT-18, pp. 395-399, May 1972.
% The procedure is described slightly differently here.
% Consider a trellis as shown below.
%              (N-3,K)  (N-5,K)
%  (N-1,K) o---o---o---o---o---o---o---o (1,2)
%           \   \   \   \   \   \   \   \
%            \   \   \   \   \   \   \   \
%             \   \   \   \   \   \   \   \
%    (N-2,K-1) o---o---o---o---o---o---o---o (0,1)
%               \   \   \   \   \   \   \   \
%                \   \   \   \   \   \   \
%                 \   \   \   \   \   \   \
%        (N-3,K-2) o---o---o---o---o---o---o (0,0)
%
% Consider the case of N positions and K pulses. The diagram is for the case
% of N=9 and K=2. The nodes are labelled with combinatorial terms indicating
% the position and how many pulses are still to be placed. We start at the
% upper left (position N-1 and K pulses) and end up at the lower right.
% Initialize the code to zero.
% (1) If a pulse appears in the first location, move diagonally down and
%     create a new subproblem with 1 fewer positions and 1 fewer pulses. Add
%     the value at the starting node to the code.
% (2) If no pulse appears in the first location, move horizontally and create
%     a new subproblem with 1 fewer position but the same number of pulses.
%     Leave the code unchanged.
% Some comments:
% (a) All possible pulse placements correspond to paths through the trellis.
%     Each diagonally downward movement indicates the position of a pulse and
%     the value of the code is sum of the nodes when moving diagonally
%     downward.
% (b) The labels on the nodes in the trellis decrease in value as we move
%     either horizontally or diagonally down to the right.
%       (n,k) > (n-1,k-1)  diagonal move [(n-1,k-1) = (n,k)-(n-1,k)]
%       (n,k) > (n-1,k)    horizontal move
%     Thus moving a pulse from one position to another changes the resulting
%     code - moving the pulse to the left increases the value of the code and
%     moving the pulse to the right decreases the code. If fact the codes are
%     in lexicographic order. If we interpret the pulse positions as binary
%     numbers, larger codes indicate a larger binary number.
% (c) The largest code is obtained when the leftmost diagonals are traversed,
%               K
%       Cmax = SUM (N-k,K-k+1) = (N,K) - 1.
%              k=1
% (d) The smallest code is obtained when the rightmost diagonals are traversed.
%       Cmin = 0.
% (e) We need to argue that the codes are unique - each pulse configuration has
%     a different code. Pick a point on a path through the trellis labelled
%     (n-1,k). Now move diagonally down due the present of a pulse. This moves
%     us to the node labelled (n-2,k-1). The subproblem generated at this point
%     will generate codes in the interval [0,(n-1,k)-1). But the amount added by
%     diagonal transition if larger than this by one. This inclusion guarantees
%     that there is a unique mapping from the sum of the values added by the
%     diagonal transitions to the locations of those transitions.
% (f) Since the codes are unique and the range of codes has been determined to
%     be in the interval [0,(N,K)-1], the codes are dense in that interval.
%
% The combinatoric coding in G.723.1 is a variant of the method described above.
% The approach taken involves updating the code for every position. In the
% approach above, the code is updated only when a pulse is encountered. Since
% the number of pulses is less than the number of non-pulses, this is more
% efficient. Furthermore one has the freedom to choose the ordering in which
% to examine the pulse train.
%
% Using the algorithm above and looking from the latest pulse to the earliest
% pulse gives a code, call it C+ that is related to the G.723.1 code (call it
% C-) by
%   C- = (N,K)-1 - C+.