C++ Algorithm Library

I would like to present you a C++ library that contains several popular numeric, text-processing, graph algorithms. I encourage you to download and use it. I will be grateful for any comment about the implemented solutions. I will continue the implementation of this library in the future, so I encourage you to follow the changes.

C++ Algorithm Library contains

  • basic and extended euclidean algorithm
  • basic and strong prefix-suffix array computation algorithm
  • max suffix computation algorithm
  • morris-pratt pattern matching algorithm
  • knuth-morris-pratt pattern matching algorithm
  • manacher’s algorithm for finding palindromes
  • union-find class
  • graph class – neighbor list and matrix representation
  • kruskal minimum spanning tree algorithm

Each algorithm was tested in separate unit-test. Unit tests are appended to repository.

OFDM modulator. Parallel processing.

Parallel processing is a non-trivial method to speed up our applications. Our computers have often two or more cores today. It is also possible to use some coprocessors like GPU or FPGA. All of this staff allows to run complex systems in the real-time.

In this post I will show you how to simply implement parallel processing in the OFDM modulator. Let’s take a look at the listings below.

void Cworking_Application_Layer::cworking_process_OFDM_modulation( Cworking_Matrix_Data& cworking_input, Cworking_Matrix_Data& cworking_output )
  /* For each symbol */
  #pragma omp parallel for
  for ( size_t cworking_symbol = 0; cworking_symbol < cworking_input.cworking_symbols; cworking_symbol++ )
    /* Create temporary symbol vector */
    Cworking_Complex_Vector cworking_symbol_output;

    /* ------------------------ OFDM Modulation ------------------------ */

    /* Calculate IFFT */
    this->cworking_dsp.muged_1D_ifft( cworking_input.cworking_radio_frame[ cworking_symbol ], cworking_symbol_output );

    /* ------------------------ OFDM Modulation ------------------------ */

    /* Store output into matrix */
    for ( size_t cworking_subcarrier = 0; cworking_subcarrier < cworking_symbol_output.length; cworking_subcarrier++ )
      /* Store single sub-carrier */
      cworking_output.cworking_radio_frame[ cworking_symbol ].array[ cworking_subcarrier ] =
      cworking_symbol_output.array[ cworking_subcarrier ];

    /* Clean memory */
    delete [] cworking_symbol_output.array;

Continue reading

Multi-layered architecture. OFDM modulator.

In previous article I briefly describe multi-layered architecture design pattern. In this post I want to show you some code which implement multi-layered architecture.

/* Main program */
int main()
	/* Declare layers */

	/* Infrastructure layer */
	Cworking_Infrastructure_Layer cworking_infrastructure;

	/* Application layer */
	Cworking_Application_Layer cworking_application;

	/* Presentation layer */
	Cworking_Presentation_Layer cworking_presentation;

	/* Declare input data */
	Cworking_Matrix_Data cworking_input_data;

	/* Declare modulated data */
	Cworking_Matrix_Data cworking_modulated_data;

	/* Declare output data */
	Cworking_Matrix_Data cworking_output_data;

	/* Initialize input and output data */
	cworking_infrastructure.cworking_allocate_matrix( cworking_input_data  );
	cworking_infrastructure.cworking_allocate_matrix( cworking_modulated_data );
	cworking_infrastructure.cworking_allocate_matrix( cworking_output_data );

	/* Load and parse input file */
	cworking_infrastructure.cworking_create_random_data( cworking_input_data );

	/* Plot chart */
	printf("\n-----------------------Input frame-----------------------\n\n");
	cworking_presentation.cworking_show_data( cworking_input_data );

	/* Run application */
	cworking_application.cworking_process_OFDM_modulation( cworking_input_data, cworking_modulated_data );

	printf("\n-----------------------Modulated frame-----------------------\n\n");
	cworking_presentation.cworking_show_data( cworking_modulated_data );

	/* Run application */
	cworking_application.cworking_process_OFDM_demodulation( cworking_modulated_data, cworking_output_data );

	printf("\n-----------------------Demodulated frame-----------------------\n\n");
	cworking_presentation.cworking_show_data( cworking_output_data );

	/* Clean memory */
	cworking_infrastructure.cworking_delete_matrix( cworking_input_data  );
	cworking_infrastructure.cworking_delete_matrix( cworking_modulated_data );
	cworking_infrastructure.cworking_delete_matrix( cworking_output_data );

	return 0;

In this listing we could distinguish infrastructure, application and presentation layers.

Infrastructure layer is responsible for data delivery. In this case it creates random radio frame with QPSK symbols. Furthermore infrastructure layer allocates and cleans memory.

Application layer is responsible for OFDM modulation and demodulation processes. OFDM modulator it is nothing other than the IFFT algorithm. Similarly OFDM demodulator it is exactly the FFT algorithm. Fast Fourier Transformation and its inverse version are implemented in separate digital signal processing library available on my GIT Hub profile [click].

Presentation layer prints the input, modulated and demodulated frames. Demodulated frame should be exactly the same as the input frame. Full code of this example is available also on my GIT Hub profile [click]. I encourage you to download the code. It will be still developed and I hope that in an interesting way.

Multi-layered Architecture

Multi-layered architecture is a software architecture where different product responsibilities are handled by separate layers. The most common layers used are: user interface and presentation layers, application and business layers, infrastructure layer. Each of them might have its own sub-layers.

User interface and presentation layers provide some multi-modal interfaces which allow users to communicate with the designed system using different methods e.g: keyboard and mouse, speech, gestures and others. Please find that this layer might be implemented as a part of a web-service, stand-alone application with or without graphical user interface. Furthermore, multi-layered architecture allows to create presentation layer before others. It might be interesting especially for the people who want to improve a usability, appearance so these parts of the product which often mostly affect customers.

Continue reading

Memory Allocator

Today I want to describe a very simple memory allocator – memory pool with fixed block size. Memory allocators are important especially for embedded systems. Such systems often require a memory management module which help to decrease memory fragmentation and provide efficient memory usage.

The idea for a simple memory management module is to allocate memory once and use it frequently. Memory allocation algorithm shouldn’t allocate any memory block outside the pool. It is possible to create more than one memory pool, e.g one memory pool for each queue.

Continue reading

3 clever macros

Today, I will show you three, clever macros. Thanks to them we can get rid of several problems. Full code and an example, as usual, are available on CWorking.

First macro: LOG

#define LOG(stream, pattern, params...) fprintf( stream,&quot;%20s:%3u | &quot; pattern &quot;\n&quot;, __FILE__, __LINE__, ##params )
#define LOG(stream, dummy, params...)

I recommend to use it especially with the DEBUG_MODE flag connected to the makefile. Thanks to that we could switch off the logger e.g by changing the project build mode from “debug” to “release”. Logger syntax is the same as fprintf, but it prints not only a formatted string, but also a filename and a line number where logger was called. It is very helpful if we want to find a source of a specific log entry. All logs can be gathered in a log file, stdout, stderr etc. thanks to the “stream” variable.

Continue reading

An interface in C++

Last time I wrote about an interface in C language. Today, I will describe how to implement an interface in C++.

In C++, like in C, we haven’t got any special keyword for an interface. We create it using an abstract class – class with at least one pure virtual function. Pure virtual function hasn’t got its own definition – implementation. It is only a declaration within the class, like below:

virtual void fun() = 0;

Pure virtual function has to be implemented in a corresponding derived class. It will be checked during the linking process. Typical interface is presented below

Continue reading

Object oriented programming in C

Everyone who ever wrote something in C certainly knows that it is a structural language. However not everyone know that object oriented programming in C is possible and quite simple. To start talking about this we need to know what is an interface and how to implement it.

An interface is a set of functions and rules which can be used to communicate with some specified object. An interface may be common for many different modules which have similar functionality. In my opinion, the most important purpose of the interface is a separation between control plane and algorithms. It is not hard to imagine that if we define interfaces for our application we can implement each module separately. The interfaces help team to cooperate and divide their work. Developer, who knows how to use all required modules before their implementation, will be more confident and will make less mistakes. Well organized project gives a greater chance to finish it earlier without sacrificing its quality.

Continue reading