Computer Science Notes For DSP Engineers

From Gracenote/ Qualcomm/ Apple/ Palm Technical Interview

  • zeros/poles location vs. stability of fir/iir
  • up/down sampling implementation
  • mdct vs. fft, which is (are) symmetric ??
  • why mfcc is rock ??
  •  

 

1.      Bitwise operations tricky related

On modern older microprocessor architectures, bitwise operations are generally the same speed as addition, though still faster than multiplication and division operations

 

Bitwise NOT, or complement, ~ in C; (logical NOT, Boolean, ! in C)

 

Bitwise OR, | in C; (logical OR, || in C)

 001011

OR  101111

= 101111

to check if the second bit is 0

 

Bitwise AND, &(ampersand); (logical AND, && in C)

  001011

AND  001000

= 001000

to check if the third bit is 1

 

Bitwise XOR, ^ in C;

0010

XOR  1010

 = 1000

used to manipulate bit patterns representing sets of Boolean variable

 

Bit shifts

Arithmetic shift: suitable for signed two¡¯s complement binary numbers

Logical shift: suitable for unsigned binary numbers

Circular shift: rotate

<< or >> in C++; (*2^n or /2^n)

 

 

Examples:

 

You have an eight bit multiply operator that takes two 8 bit numbers and returns a 16 bit value. Given two 16 bit values stored in 32 bit int variables, find the product using the 8 bit multiply operator.

 

int multiply8bit(int m, int n)
{
   int mLow_nLow = (m & 0x00FF) * (n & 0x00FF);
   int mHigh_nLow = ((m & 0xFF00)>>8) * (n & 0x00FF);
   int mLow_nHigh = (m & 0x00FF) * ((n & 0xFF00)>>8);
   int mHigh_nHigh = ((m & 0xFF00)>>8) * ((n & 0xFF00)>>8);
   return mLow_nLow + (mHigh_nLow<<8) + (mLow_nHigh<<8) + (mHigh_nHigh<<16);
}

 

Swap bits in position i and j for a number

if (( (n&(1<<i))>>i)^((n&(1<<j))>>j) {
  n^=(1<<i);
  n^=(1<<j);
}
return n;

//If two bits are different, we just need to flip those two bits

Count number of binary 1s in a number

int nos_of_ones(int n){
int count = 0;
while (n!=0){
if (n&1){
count++;
}
n>>1;
}
return (count);
}

 

Reverse the bit representation of an integer questions abt stack/heap/recursion etc.

 

//XOR with all 1s

10110001 XOR 11111111 = 01001110

 

 

1.     Memory Layout (Where are Global, Static and Local Variables allocated in the memory?)

 

Global and Static variables:   Stored in BSS (Block Started by Symbol) section of the data segment. (static memory area)

Local variables:   Stored on the stack and are valid until the program exits from the function in which they are defined. (dynamic memory area- STACK)

Static Local variables:  Static variables in a function, for example, are initialized just once while compiling. Default is 0. We could use static local variables to compute nth factorial, because it will

                                      not free the static n after calling the function each time. It will remain in the static memory area until the program ends.

Static Global variables:   only valid in the modular file where they are defined, so that hidden from other modular. (The scope/visibility is limited to that particular file)

 

Memory Layout

 

Picture of Memory Organization
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Load and store operations copy the bit pattern from the source into the destination. The source (register or memory) does not change. Of course, the pattern at the destination is replaced by the pattern at the source.

Memory is built to store bit patterns. Both instructions and data are bit patterns, and either of these can be stored anywhere in memory (at least, so far as the hardware is concerned.) However, it is convenient for programmers and systems software to organize memory so that instructions and data are separated. At right is the way MIPS operating systems often lay out memory.

Although the address space is 32 bits, the top addresses from 0x80000000 to 0xFFFFFFFF are not available to user programs. They are used for the operating system and for ROM. When a MIPS chip is used in an embedded controller the control program exists in ROM in this upper half of the address space.

The parts of address space accessible to a user program are divided as follows:

Text Segment: This holds the machine language of the user program (the text).

Data Segment: This holds the data that the program operates on. Part of the data is static. This is data that is allocated by the assembler and whose size does not change as a program

                executes. Values in it do change; "static" means the size in bytes does not change during execution. On top of the static data is the dynamic data. (HEAP), this is data

                             that is allocated and deallocated as the program executes. In "C" dynamic allocation and deallocation is done with malloc() and free(). (calloc() and realloc())

                The return values of these allocation functions are the initial address of the allocated memory. (values of pointer variables)

Stack Segment: At the top of user address space is the stack. With high level languages, local variables and parameters are pushed and popped on the stack as procedures are activated

  and deactivated.

 

2.      Terminology & Trivia

lated tatic and Local Variable  Boolean variablVolatile: A variable or object declared with the volatile may be modified externally from the declaring object. Variables declared to be volatile will not be optimized by the compiler because the computer must assume that their values can change at any time.

Memory operation: memmove() and memcpy() (coming soon¡­)

 

Process V.S. Threads

Process is an instance of a program (needs executable). Thread is an execution of a C-function. A process has its own address space, heap, code memory, data memory, global memory. Each thread has its own stack, thread specific variables, thread context (such as registers, program counter). Memory space of one process does not overlap with that of other process. A process can contain multiple threads. All the threads within a process share the process's memory space. If a thread changes a global variable (memory), other threads accessing global variable will read updated value. Thus, inter-task communication is simpler. The inter-task context switching has less overhead. Whereas, inter-process context switching has more overhead. There is no hierarchy among threads within same process (parent-child-grand child hierarchy).

 

 

Home Page