# v_huffman

## PURPOSE

V_HUFFMAN calculates a D-ary v_huffman code [CC,LL]=(P,A)

## SYNOPSIS

function [cc,ll,l]=v_huffman(p,a)

## DESCRIPTION

    V_HUFFMAN calculates a D-ary v_huffman code [CC,LL]=(P,A)

      Inputs:  P        is a vector or matrix of probabilities
               A(D)     is a vector of alphabet characters either integers of chars [default: '01']
                        the length of A determines the order of the code

     Outputs:  CC       is a cell array containing the code for each symbol with the sme shape as P
               LL       is a vector or matrix of code lengths with the sme shape as P
               L        is the average code length

## CROSS-REFERENCE INFORMATION

This function calls:

This function is called by:

## SOURCE CODE

    0001 function [cc,ll,l]=v_huffman(p,a)
    0002 %V_HUFFMAN calculates a D-ary v_huffman code [CC,LL]=(P,A)
    0003 %
    0004 %  Inputs:  P        is a vector or matrix of probabilities
    0005 %           A(D)     is a vector of alphabet characters either integers of chars [default: '01']
    0006 %                    the length of A determines the order of the code
    0007 %
    0008 % Outputs:  CC       is a cell array containing the code for each symbol with the sme shape as P
    0009 %           LL       is a vector or matrix of code lengths with the sme shape as P
    0010 %           L        is the average code length
    0011
    0012 %       Copyright (C) Mike Brookes 1995
    0013 %      Version: $Id: v_huffman.m 10865 2018-09-21 17:22:45Z dmb $
    0014 %
    0015 %   VOICEBOX is a MATLAB toolbox for speech processing.
    0016 %   Home page: http://www.ee.ic.ac.uk/hp/staff/dmb/voicebox/voicebox.html
    0017 %
    0018 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    0019 %   This program is free software; you can redistribute it and/or modify
    0020 %   it under the terms of the GNU Lesser General Public License as published by
    0021 %   the Free Software Foundation; either version 3 of the License, or
    0022 %   (at your option) any later version.
    0023 %
    0024 %   This program is distributed in the hope that it will be useful,
    0025 %   but WITHOUT ANY WARRANTY; without even the implied warranty of
    0026 %   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    0027 %   GNU Lesser General Public License for more details.
    0028 %
    0029 %   You can obtain a copy of the GNU Lesser General Public License from
    0030 %   https://www.gnu.org/licenses/ .
    0031 %
    0032 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    0033
    0034 np=length(p(:));
    0035 if nargin <2
    0036     a='01';
    0037 end
    0038 d=length(a);
    0039
    0040 % first append additional zeros-probability symbols to ensure a full code tree
    0041
    0042 nx=np+mod(1-np,d-1);
    0043 px=zeros(nx,1);
    0044 px(1:np)=p(:);
    0045
    0046 cl=(nx-1)/(d-1);        % max potential code length
    0047 cd=zeros(nx,cl);        % code array
    0048 qx=px;
    0049 ix=(1:nx)';
    0050 dd=(d:-1:1)';
    0051 kx=zeros(nx,1);
    0052 for i=cl:-1:1
    0053     nc=1+i*(d-1);
    0054     [rx,jx]=sort(qx);   % find the D smallest probabilities
    0055     kx(jx)=(1:nc)';          % create a reverse index
    0056     cd(:,i)=kx(ix);
    0057     ix=max(kx(ix)-d+1,1);
    0058     rx(d)=sum(rx(1:d));
    0059     qx=rx(d:end);
    0060 end
    0061 cc=cell(size(p));
    0062 ll=zeros(size(p));
    0063 for i=1:np
    0064     ci=cd(i,cd(i,:)<=d);
    0065     ll(i) = length(ci);
    0066     cc{i}=a(ci);
    0067 end
    0068 l=p(:)'*ll(:)/sum(p(:));      % calculate average length