Matlab to VHDl accelDSP error

Dear all, I have written a huffman .m file which do huffman text compression where the input is frequency of occurrence of characters. And I want to change this matlab file to VHDL using accelDSP but in my code there are functions 'strcat' and 'sort' where accelDSP can't synthesize. So I want the code below to do the same purpose but with 'strcat' , 'sort' and 'strfind' done by other equivalent functions so that the code will be synthesizable by accelDSP.

SAMPLE OUTPUT OF the accelDSP during matlab to vhdl change is

#(E-ANALYZE-0022): C:\Documents and Settings\Tadele\Desktop\Huffman_accelDSP\huff2\huffmanFunction.m(77): Unsupported built-in function call: "strcat"

%%Huffman Encoding Example
% The goal of this program is to demonstrate the construction of a huffman encoding tree.
% The tree is represented as a binary tree using MATLAB's built in treeplot commands.
% Contruction of the tree as well as the huffman code book will be described in later sections.

%%Initial Setup 
% The first piece of code in this program initializes the MATLAB console by clearing
% all existing state (variables, figures, etc.)

clc;
clear all;
close all;

%%User-Defined Input
% The user is able to define the string that they wish to huffman encode.
% The probability distribution for individual characters can either be automatically calculated
% based on the character's ASCII values, or can be manually inputted by the user

% Define the character string
my_str = 'sauhfemyz.qnotlr cidgbp';

%%Probability Calculation Flag
% Flag used to enable auto-calculation of probabilities
% * 1 = Auto-calculate
% * 0 = User-defines probabilities manually
%auto_prob = 1;

%if (auto_prob == 1) 
    % Automatically calculate the probability distribution
    % Get ASCII version of each character
    %   Each ASCII value represents the probability of finding the character
   % prob_dist = double(my_str);
%else
    % Manually define the probability distribution
    prob_dist = [32 17 9 9 18 42 10 5 1 2 3 21 23 13 13 26 56 16 15 14 7 4 3];
%end

%%Encoding Bit Calculation
% Calculate the number of bits to encode with.  In a binary system it takes n-bits to encode 2^n items, 
% so the number of bits to use in the huffman encoder is simply the log-base2 of the number of items to encode.
num_bits = ceil(log2(length(prob_dist)))

%%Console Output - Initial Characters and Their Respective Probabilties
% Display character vs. probability
disp('Character Probability:');
for i = 1:length(prob_dist)
    display(strcat(my_str(i),' -->  ',num2str(prob_dist(i))));
end
total = sum(prob_dist)

%%Initialize The Encoding Array

for i = 1:length(my_str)
    sorted_str{i} = my_str(i);
end

% Save initial set of symbols and probabilities for later use
init_str = sorted_str;
init_prob = prob_dist;

%%Huffman Encoding Process
sorted_prob = prob_dist;
rear = 1;
while (length(sorted_prob) > 1)
    % Sort probs
    [sorted_prob,indeces] = sort(sorted_prob,'ascend');

      % Sort string based on indeces
      sorted_str = sorted_str(indeces);
      % Create new symbol
      new_node = strcat(sorted_str(2),sorted_str(1));
      new_prob = sum(sorted_prob(1:2));
      % Dequeue used symbols from "old" queue
      sorted_str =  sorted_str(3:length(sorted_str));strcat
      sorted_prob = sorted_prob(3:length(sorted_prob));
      % Add new symbol back to "old" queue
      sorted_str = [sorted_str, new_node];
      sorted_prob = [sorted_prob, new_prob];
      % Add new symbol to "new" queue
      newq_str(rear) = new_node;
      newq_prob(rear) = new_prob;
      rear = rear + 1;
  end
%%Form Huffman Tree Data
% Get all elements for the tree (symbols and probabilities) by concatenating
% the original set of symbols with the new combined symbols and probabilities
tree = [newq_str,init_str];
tree_prob = [newq_prob, init_prob];

% Sort all tree elements
[sorted_tree_prob,indeces] = sort(tree_prob,'descend');
sorted_tree = tree(indeces);

%%Calculate Tree Parameters
% Calculate parent relationships for all tree elements.
% This will allow the treeplot command to realize the correct tree structure.
parent(1) = 0;
num_children = 2;
for i = 2:length(sorted_tree)
    % Extract my symbol
    me = sorted_tree{i};

      % Find my parent's symbol (search until shortest match is found)
      count = 1;
      parent_maybe = sorted_tree{i-count};
      diff =strfind(parent_maybe,me);
      while (isempty(diff))
          count = count + 1;
          parent_maybe = sorted_tree{i-count};
          diff = strfind (parent_maybe,me);
      end
      parent(i) = i - count;
  end
%%Plot the Huffman Tree
% This is easily done using the treeplot command whose argument is
% the array that contains the parent relationships for each node.
treeplot(parent);
title(strcat('Huffman Coding Tree - "',my_str,'"'));

%%Console Output - Tree Symbols and Their Probabilities
% Print out tree in text form
display(sorted_tree)
display(sorted_tree_prob)

%%Tree Parameter Extraction
% Extract binary tree parameters.  These parameters include the (x,y) coordinates
% of each node so that we can accurately place label on the tree.
[xs,ys,h,s] = treelayout(parent);

%%Label Tree Nodes
% Place labels on each tree node
text(xs,ys,sorted_tree);

%%Label Tree Edges
% Put weights on the tree.  The slope of each edge indicates whether it is a 
% left-branch or a right-branch.  Left-branches have positive slope and are
% labelled with a '1', while right-branches have negative slope and are labelled
% with a '0'.  The labels for the weights are placed at the midpoint of each edge. 
% Calculate mid-points for each node
for i = 2:length(sorted_tree)
    % Get my coordinate
    my_x = xs(i);
    my_y = ys(i);

      % Get parent coordinate
      parent_x = xs(parent(i));
      parent_y = ys(parent(i));
      % Calculate weight coordinate (midpoint)
      mid_x = (my_x + parent_x)/2;
      mid_y = (my_y + parent_y)/2;
      % Calculate weight (positive slope = 1, negative = 0)
      slope  = (parent_y - my_y)/(parent_x - my_x); 
      if (slope > 0)
          weight(i) = 0;
      else
          weight(i) = 1;
      end
      text(mid_x,mid_y,num2str(weight(i)));
  end
%%Huffman Codebook Calculation
for i = 1:length(sorted_tree)
    % Initialize code
    code{i} = '';

      % Loop until root is found
      index = i;
      p = parent(index);
      while(p ~= 0)
          % Turn weight into code symbol
          w = num2str(weight(index));
          % Concatenate code symbol
          code{i} = [w,code{i}];   %strcat
          % Continue towards root
          index = parent(index);
          p = parent(index);  
      end
  end
codeBook = [sorted_tree', code']

Eager to hear the answer, Thanks

Answer 1

[Walter Roberson]

Your w is a pure string, and your code{i} appears to be a pure string, so the line

code{i} = strcat(w,code{i});

could be replaced by

code{i} = [w, code{i}];

Likewise, your line

display(strcat(my_str(i),' -->  ',num2str(prob_dist(i))));

can be replaced by

display([my_str(i), ' --> ', num2str(prob_dist(i))]);

sort() is not so easily replaced, at least not efficiently.

Answer 2

[Tadele Gerem]

Dear Walter Roberson, Thanks for your fast respons,and I have checked what you recommend me about 'strcat' and it perfectly works for the specific line of code I replaced.

And pls do help me for the 'strfind','strcat' for the other lines and 'sort' whatever the efficiency might be.

hopefully waiting your fast response as usual thanks

[Walter Roberson]

You can replace all of the strcat() calls you have with horzcat() calls.

I notice that you do not use the return value from strfind() except to check whether it is empty or not. Are you looking for a match at the beginning of the string or a match anywhere in the string or a match at the end of the string? A match at the beginning or end of the string is pretty easy to program -- check to be sure the string is at least as long as the pattern and then check whether the appropriate part of the string isequal() to the pattern.

With regards to the sort: my recollection is that you do not need to sort() at all if you are smart about how you insert the values in to the tree.

Anyhow, you should be able to google up a matlab sort routine easily -- it is a first-term sort of assignment.

[Tadele Gerem]

Dear Walter Roberson,

I tried to add this code in place of the sort function but I cant figure out how I can calculate the indeces

pls help me .

sorted_prob = prob_dist;

y = length(sorted_prob);

sorted = 0;

n = 0;

while ~sorted

sorted = 1;

for i = 1:y-1

if sorted_prob(i) > sorted_prob(i+1)

n = n + 1;

t = sorted_prob(i);

sorted_prob(i) = sorted_prob(i+1);

sorted_prob(i+1) = t;

sorted = 0;

end

end

end

[Walter Roberson]

Sorry, was up late again last night answering questions, and I am too foggy at the moment to work through this. Possibly someone else will have a clear mind before I have a chance to look at it.

[Tadele Gerem]

Dear Walter,

I am desperatly in need of ur help as I am running out of time.

I tried to add this code in place of the sort function but I cant figure out how I can calculate the indeces

pls help me .

sorted_prob = prob_dist;

y = length(sorted_prob);

sorted = 0;

n = 0;

while ~sorted

sorted = 1;

for i = 1:y-1

if sorted_prob(i) > sorted_prob(i+1)

n = n + 1;

t = sorted_prob(i);

sorted_prob(i) = sorted_prob(i+1);

sorted_prob(i+1) = t;

sorted = 0;

end

end

end

Thank you

[Walter Roberson]

Sorry, I'm at work and have crucial paperwork to do.