Modified Uniformly Redundant Array

Last updated March 19, 2022

A modified uniformly redundant array (MURA) is a type of mask used in coded aperture imaging. They were first proposed by Gottesman and Fenimore in 1989.^[1]

Mathematical Construction of MURAs

MURAs can be generated in any length L that is prime and of the form

L=4m+1,\ \ m=1,2,3,...,

the first five such values being $L=5,13,17,29,37$ . The binary sequence of a linear MURA is given by $A={A_{i}}_{i=0}^{L-1}$ , where

A_{i}={\begin{cases}0&{\mbox{if }}i=0,\\1&{\mbox{if }}i{\mbox{ is a quadratic residue modulo }}L,i\neq 0,\\0&{\mbox{otherwise}}\end{cases}}

These linear MURA arrays can also be arranged to form hexagonal MURA arrays. One may note that if $L=4m+3$ and $A_{0}=1$ , a uniformly redundant array(URA) is a generated.

As with any mask in coded aperture imaging, an inverse sequence must also be constructed. In the MURA case, this inverse G can be constructed easily given the original coding pattern A:

G_{i}={\begin{cases}+1&{\mbox{if }}i=0,\\+1&{\mbox{if }}A_{i}=1,i\neq 0,\\-1&{\mbox{if }}A_{i}=0,i\neq 0,\end{cases}}

Rectangular MURA arrays are constructed in a slightly different manner, letting $A=\{A_{ij}\}_{i,j=0}^{p-1}$ , where

A_{ij}={\begin{cases}0&{\mbox{if }}i=0,\\1&{\mbox{if }}j=0,i\neq 0,\\1&{\mbox{if }}C_{i}C_{j}=+1,\\0&{\mbox{otherwise,}}\end{cases}}

and

C_{i}={\begin{cases}+1&{\mbox{if }}i{\mbox{ is a quadratic residue modulo }}p,\\-1&{\mbox{otherwise,}}\end{cases}}

The corresponding decoding function G is constructed as follows:

G_{ij}={\begin{cases}+1&{\mbox{if }}i+j=0;\\+1&{\mbox{if }}A_{ij}=1,\ (i+j\neq 0);\\-1&{\mbox{if }}A_{ij}=0,\ (i+j\neq 0),;\end{cases}}

Related Research Articles

In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo an odd prime number p: its value at a (nonzero) quadratic residue mod p is 1 and at a non-quadratic residue (non-residue) is −1. Its value at zero is 0.

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

Quadratic reciprocity Gives conditions for the solvability of quadratic equations modulo prime numbers

In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard statement is:

The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837, it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in turn are important in cryptography.

Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, a generalization of pigeonhole sort that allows multiple keys per bucket, and is a cousin of radix sort in the most-to-least significant digit flavor. Bucket sort can be implemented with comparisons and therefore can also be considered a comparison sort algorithm. The computational complexity depends on the algorithm used to sort each bucket, the number of buckets to use, and whether the input is uniformly distributed.

In modular arithmetic, a number $g$ is a primitive root modulo $n$ if every number $a$ coprime to $n$ is congruent to a power of $g$ modulo $n$ . That is, $g$ is a primitive root modulo $n$ , if for every integer $a$ coprime to $n$ , there is some integer $k$ for which $g$ ^$k$ ≡ $a$ . Such a value $k$ is called the index or discrete logarithm of $a$ to the base $g$ modulo $n$ . So $g$ is a primitive root modulo $n$ if and only if $g$ is a generator of the multiplicative group of integers modulo $n$ .

In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that:

Bruun's algorithm is a fast Fourier transform (FFT) algorithm based on an unusual recursive polynomial-factorization approach, proposed for powers of two by G. Bruun in 1978 and generalized to arbitrary even composite sizes by H. Murakami in 1996. Because its operations involve only real coefficients until the last computation stage, it was initially proposed as a way to efficiently compute the discrete Fourier transform (DFT) of real data. Bruun's algorithm has not seen widespread use, however, as approaches based on the ordinary Cooley–Tukey FFT algorithm have been successfully adapted to real data with at least as much efficiency. Furthermore, there is evidence that Bruun's algorithm may be intrinsically less accurate than Cooley–Tukey in the face of finite numerical precision.

In mathematics, in the area of number theory, a Gaussian period is a certain kind of sum of roots of unity. The periods permit explicit calculations in cyclotomic fields connected with Galois theory and with harmonic analysis. They are basic in the classical theory called cyclotomy. Closely related is the Gauss sum, a type of exponential sum which is a linear combination of periods.

In number theory, the Kronecker symbol, written as $or, is a generalization of the Jacobi symbol to all integers . It was introduced by Leopold Kronecker.$

In the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. Named after Pierre-Simon Laplace, the graph Laplacian matrix can be viewed as a matrix form of the negative discrete Laplace operator on a graph approximating the negative continuous Laplacian obtained by the finite difference method.

Gauss's lemma in number theory gives a condition for an integer to be a quadratic residue. Although it is not useful computationally, it has theoretical significance, being involved in some proofs of quadratic reciprocity.

In number theory, the law of quadratic reciprocity, like the Pythagorean theorem, has lent itself to an unusually large number of proofs. Several hundred proofs of the law of quadratic reciprocity have been published.

In numerical linear algebra, the Jacobi eigenvalue algorithm is an iterative method for the calculation of the eigenvalues and eigenvectors of a real symmetric matrix. It is named after Carl Gustav Jacob Jacobi, who first proposed the method in 1846, but only became widely used in the 1950s with the advent of computers.

In mathematics, an elementary matrix is a matrix which differs from the identity matrix by one single elementary row operation. The elementary matrices generate the general linear group GL_n(F) when F is a field. Left multiplication (pre-multiplication) by an elementary matrix represents elementary row operations, while right multiplication (post-multiplication) represents elementary column operations.

In mathematics, the Hilbert symbol or norm-residue symbol is a function from K^× × K^× to the group of nth roots of unity in a local field K such as the fields of reals or p-adic numbers. It is related to reciprocity laws, and can be defined in terms of the Artin symbol of local class field theory. The Hilbert symbol was introduced by David Hilbert in his Zahlbericht, with the slight difference that he defined it for elements of global fields rather than for the larger local fields.

In mathematics, the Grothendieck inequality states that there is a universal constant $with the following property. If M ij is an n \times n matrix with$

A quadratic residue code is a type of cyclic code.

In mathematics, elliptic curve primality testing techniques, or elliptic curve primality proving (ECPP), are among the quickest and most widely used methods in primality proving. It is an idea put forward by Shafi Goldwasser and Joe Kilian in 1986 and turned into an algorithm by A. O. L. Atkin the same year. The algorithm was altered and improved by several collaborators subsequently, and notably by Atkin and François Morain, in 1993. The concept of using elliptic curves in factorization had been developed by H. W. Lenstra in 1985, and the implications for its use in primality testing followed quickly.

The quadratic knapsack problem (QKP), first introduced in 19th century, is an extension of knapsack problem that allows for quadratic terms in the objective function: Given a set of items, each with a weight, a value, and an extra profit that can be earned if two items are selected, determine the number of items to include in a collection without exceeding capacity of the knapsack, so as to maximize the overall profit. Usually, quadratic knapsack problems come with a restriction on the number of copies of each kind of item: either 0, or 1. This special type of QKP forms the 0-1 quadratic knapsack problem, which was first discussed by Gallo et al. The 0-1 quadratic knapsack problem is a variation of knapsack problems, combining the features of unbounded knapsack problem, 0-1 knapsack problem and quadratic knapsack problem.

References

↑ Fenimore, E. E.; Gottesman, Stephen R. (1989-10-15). "New family of binary arrays for coded aperture imaging". Applied Optics. 28 (20): 4344–4352. doi:10.1364/AO.28.004344. ISSN 2155-3165.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Fenimore, E. E.; Gottesman, Stephen R. (1989-10-15). "New family of binary arrays for coded aperture imaging". Applied Optics. 28 (20): 4344–4352. doi:10.1364/AO.28.004344. ISSN 2155-3165.

[1]