[Matlab] M-Ary Quadrature Signal Modulation Decision Region Generator

https://github.com/walter426/Matlab_DSMA_Utilities/tree/master/DSMA_Utilities/M_Ary_QSMDR_Generator


 As mentioned in the title, it is a Digital Signal Processing stuff, but it can be applied to other fields which need to determine any 2D decision regions... (It sounds shit to laymen...)

Below is a brief lesson for background started from the point of view under signal processing.

Fig 1: Constellation Diagram

During a physical communication, a set of signals called Modulation Scheme is used to indicate information(e.g. '00', '11', '10...) to be transmitted. The signal in a Modulation Scheme can be represented by a set of orthogonal signals called Signal Space. The number of the orthogonal  signals is thus the number of dimensions of the signal space. Then, a Modulation Scheme can be represented as a set of point symbol in the Signal Space that is called a Constellation Diagram.

Fig.2: Decision Region

During a transmission, it is normal that the signal will suffer noise from the environment, that represents as a displacement of symbol in the Signal Space. If Noise is high enough, the transmitted symbol may be shifted to a location close to other symbol so that the receiver will de-modulate out wrong symbol. So it is important to keep sufficient distance between each signal symbol pairs in the Modulation Scheme in the signal space if noise is quite high. The distance implies each symbol has its own optimal decision region in the signal space to minimize the Symbol Error Ratio and thus the Bit Error Rate.



Now make a break of the lesson, let me recall the aim of the M-Ary Quadrature Signal Modulation Decision Region Generator(M-Ary QSMDR Generator). The aim of the M-Ary QSMDR Generator is to "Draw Optimal Decision Regions of any number of Signal Symbol in a 2-Dimensional Signal Space".


Below is the brief description of the main project files,
M_Ary_QSMDR_Generator.m: Create Arguments(e.g. Signal Set, Probability Set) for SignalSymbolDecisionRegionGenerator.m
SignalSymbolDecisionRegionGenerator.m: Create and Draw the Decision Regions of the input Signal Symbol.
SignalSymbolDecisionBdry.m: Create Decision Boundary between two signal symbols with given probabilities of the symbols and the Additive White Gaussian Noise(AWGN) .


Based on previous background and description, it's time to explain the algorithm which is implemented in SignalSymbolDecisionRegionGenerator.m.

A. Create Boundary Line between Signal Symbol pair:
- Every Signal Symbol pair are put into SignalSymbolDecisionBdry.m to create its Decision Boundary based on below criteria.

Fig 3. Decision Boundary Criteria

Fig 4: Decision Regions before truncation

After all boundary line are drawn, it is obvious that every signal symbol need the boundary segments closest to it only. The other boundary segments can be truncated on the diagram.

At this step, the optimal decision region problem becomes a Geometry problem. 

B. Cut unnecessary boundary segment
To be honest, it is not easy to archive this task. Fortunately, I found out this is possible if treat the lines in the constellation diagram as vectors. By comparing the angles between those vectors, it is possible to get which boundary segments are closest to the symbol. Below is the Vector Angle Comparison Criteria.

By above Four criteria, the unnecessary boundary segments is able to be determined, and then truncated on the Decision Region diagram.


Below are some examples of the Decision Region generated,

Comment:
This stuff is the most difficult project I have ever made before...
The difficulty is on the discovery on the relations between symbols and their intercepted boundary lines...

[Matlab] N X N Sudoku Solver

A few yrs ago, a mathematician created above sudoku, he claims it is the hardest sudoku at that time. For interest, I tried to create an algorithm to solve this stuff.

Due to my laziness, I had created the logic part a year ago, but just have finsihed the guessing part of the algorithm recently.

Below is my algorithim to solve N x N sudoku, where N = n^2, n is positive integer.
N is set as 9, the usaul size of most of sudoku.

In my current acknowledgement, the algorithm to solve a sudoku can be divided into two parts mainly --- Logical Deduction And Guessing.

Logical Deduction:
 As the title mentions, logically deduct the candidates of each unfilled blocks for one or many iterations, untill all the blocks are filled. Below is the algorithm

A. Omit Candidates of each unfilled blocks one by one.
a. list all the potential candidates(1-9) of each block

b. Check the row, column and the local 3x3 matrix of the blocks belonging, omit the impossible candidates

c. If only one candidates is left, fill the block.

d. If all the other blocks of the row, column, or the local 3x3 matrix are filled, then fill in the block with the right candidate.

e. if no cnadidate is left, then the solution is determined as wrong.

f. Redo above process untill the sudoku is finished or checked as wrong.


B. Omit Candidates in a local 3x3 matrix if the N blocks in a row or column of a local matrix have N candidates.
There are some cases that the algorithim part A cannot process further. The algorithim part B was created to handle these cases.

a. If there are N blocks in the same row or column of a local 3x3 matrix, all of them have N identical candidates.It implies the other two local rows and columns should not have these candidates. Then, omit these candidates from the other two local rows or columns.


Combing above two algorithm, this Logical Deduction algorithm can finish most of the sudoku.
---------------------------------------------------------------------------------------------------------------------------------

However, there are still some sudoku like the hardest one require guessing.
Below is the algorithm of the Generic Sudoku Solver.

2. Generic Sudoku Solver:
a. Solve the sudoku by Logical Deduction

b. If not finished or still correct, continue to step, c).

c. Count the possible candidates of each blocks

d. Select the block with the least candidates, then fill in one of the candidate, do the Generic Sudoku Solver with the new sudoku recursively.

e. if the returend sudoku is correct and complete, then stop the process.


By this algorithm, only three seconds and 114 times of guessing to solve this sudoku.
below is my answer

As Matrix is excellent for matrix operations, so Matlab was used to implement this algorithm.
Below is the code reference.
https://github.com/walter426/Matlab_SudokuSolver/