Thread: Convolution in c

  1. #1
    Registered User
    Join Date
    Feb 2011
    Posts
    39

    Cool Convolution in c

    Hi, I have to do an assignment for my C programming class. I have to write a function that takes two arrays as arguments, calculates their discrete convolution and prints out the resulting function in 2 columns. It should do the calculation only for non-zero numbers. The problem is that I don't even know how a convolution works, i'm just taking calculus right now.
    can anybody help? I would appreciate it

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    google for "discrete convolution". There is plenty of information out there.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  3. #3
    Registered User
    Join Date
    Feb 2011
    Posts
    39
    well, I've done that already, the problem is how to make it into a C, I don't even know what the output is supposed to look like

  4. #4
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Well, your first step is to understand what the output of a discrete convolution process is supposed to be. Once you understand that, you will be able to design an appropriate algorithm (description of logical steps to get from inputs to outputs). Once you understand the algorithm, implementing it in C should be simple.

    But it is impossible to write code in any programming language if you cannot describe what that code is required to achieve.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    So you managed to google "discrete convolution" but you couldn't manage "discrete convolution c source code" ?

    > I don't even know what the output is supposed to look like
    Two columns of numbers, according to your first post.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Do you know what a dot product is?
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  7. #7
    Registered User
    Join Date
    Jul 2010
    Location
    Oklahoma
    Posts
    107
    I've also heard dot product called an inner product too, I mean as opposed to a cross product. These were part of a complete college algebra, of course sometimes the conic section is so overwhelming that the class doesn't make it to them. I think the professor ended up calling those questions extra credit on the final anyway.

    Best Regards,
    Kept the text books....
    Went interdisciplinary after college....
    Still looking for a real job since 2005....

    During the interim, I may be reached at ELance, vWorker, FreeLancer, oDesk and WyzAnt.

  8. #8
    Registered User
    Join Date
    Feb 2011
    Posts
    39
    sorry for the delay.
    Can anybody give me an small example? using the convolution of matrices (i'm not asking for the answer) so maybe that can be more helpful

  9. #9
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by torquemada View Post
    sorry for the delay.
    Can anybody give me an small example? using the convolution of matrices (i'm not asking for the answer) so maybe that can be more helpful
    You have two arrays of values which you are convolving together. For the sake of example, assume they are one-dimensional, though higher dimensions work the same way. One of the arrays is typically much larger than the other. The one which is larger is called the 'signal', by convention. The smaller one is called the 'kernel'. To convolve them, you take the kernel and slap it down on top of the signal somewhere. You take the dot product of the two, this produces a result. This is one data point of the convolution. Now you slide the kernel to the right (or left, whatever) by one sample, and do it again. That produces the next data point. And so on, until the kernel 'slides off' the end of the signal.

    There are details that I won't go into, such as the kernel is the time-reversed impulse response of the filter, the length of the result is N + M - 1 where N is the signal length and M is the kernel length, etc. Since this is a programming assignment, I assume that those particular details are not really the point of the assignment.

    The biggest hint that I can give you is that you are going to need one loop nested inside another loop.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  10. #10
    Registered User
    Join Date
    Feb 2011
    Posts
    39

    Cool

    Hi, it's been a while since I started this thread but I've been busy. I was working on my program and I got something but it gives me the wrong output. My professor said the output should be as follows.
    f*f[0] = 0, f*f[i] = 0, f*f[2] = 16, f*f[3] = 64 and so on
    my program compiles but it gives me outputs like this
    nnindex: 0 convolution -1019395280
    index: 0 convolution -1438002336
    index: 1 convolution 0
    index: 1 convolution -626327120


    her is my source code if anyone would like to help me
    Code:
        #include<stdio.h>
    
    
    void mult( int f[], int g[], int n){ /*function to multiply  first array by 4*/
    
            int i;
            for (i =0; i < n; i++){
                    g[i] = 4 * f[i];
                    printf("n");
    
            }
    }
    
    
    void convo(int f[], int g[], int  h[], int n){  /*function to convolve the 2 arrays*/
    
            int i, j;
    
            for(i = 0; i < n; i++){
                h[i] = 0;
                for(j = 0; j < n; j++){
                  if (g[j]-f[i]>0){
                        h[i] += f[i]*(g[j]-f[i]);  /*convolve the two arrays*/
                            printf("index: %d\t convolution %d\n", i, h[i]);
                            }
                }
        }
    }
    
    int main()
    {
            int n;
    
            printf("enter the number of elements in the array: ");
            scanf("%d", &n);
    
            int f[n];
            int g[n];
    
            mult(f, g, n);
    
            int h[n];
            convo(f, g, h, n);
            return 0;
    
    }

  11. #11
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > g[i] = 4 * f[i];
    So what did you store in the f array between declaring it in main() and using it here in this function?

    At the moment, it looks like garbage data.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  12. #12
    Registered User
    Join Date
    Feb 2011
    Posts
    39

    Cool

    Quote Originally Posted by Salem View Post
    > g[i] = 4 * f[i];
    So what did you store in the f array between declaring it in main() and using it here in this function?

    At the moment, it looks like garbage data.
    well the output is garbage, so the input must garbage too
    im storing the numbers from 0 to n where n is an input from the keyboard

    g[i] = 4* f[i]; is supposed to be part of the entire output, by this I mean the out put is suppose to be every 4 ( meaning every given interval, in this case 4)

    the 2 functions given to create the program are
    (f *g)[n] = integral of f(i)*g(j-i) in the interval from - infinity to positive in finity

    the other function is f(n) = {4n: [0,N]
    {0: otherwise
    where n is an input from keyboard and
    N defines the end of the interval to be computed


    I understand that for the convolution works by taking an array and multiplying it by another array (in this case itself) whose elements are flipped and and slipped underneath the first array n positions to the left until you are at the position desired and then multiplying the 2 arrays to get the final value. (correct me if I'm wrong, or maybe just couldn't be more specific)

  13. #13
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > well the output is garbage, so the input must garbage too
    > im storing the numbers from 0 to n where n is an input from the keyboard
    Feel free to post some code with a scanf call (or indeed any kind of input) to show us what you're doing.

    You get the best answers when you copy/paste your code from your editor, and copy/paste your program run from your terminal.
    Then we can see exactly what you did, and have a good chance at being able to replicate it as well.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  14. #14
    Registered User
    Join Date
    Feb 2011
    Posts
    39
    My program is not supposed to ask for any inputs besides the value for n which represents the limit of the array. The values to be evaluated are the values of "i", which range form 0 to n where n is the limit of the array. for example the first number would be 0 since "i" it starts at 0, then 1, 2 and so on.

  15. #15
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    You have NEVER set the values of the array F[] in any of the code you have posted.
    That is what the others are trying to make you understand.

    Tim S.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Convolution in C
    By rrr in forum C Programming
    Replies: 2
    Last Post: 01-19-2011, 05:34 PM
  2. FFT and convolution
    By DavidP in forum General Discussions
    Replies: 7
    Last Post: 07-03-2009, 09:31 AM
  3. Caught In The Convolution Matrix
    By SMurf in forum Game Programming
    Replies: 3
    Last Post: 11-25-2007, 10:24 PM