Coding for information storage

Storage systems are widely used and have played a crucial rule in both consumer and industrial products, for example, personal computers, data centers, and embedded systems. However, such system suffers from issues of cost, restricted-lifetime, and reliability with the emergence of new systems and devices, such as distributed storage and flash memory, respectively. Information theory, on the other hand, provides fundamental bounds and solutions to fully utilize resources such as data density, information I/O and network bandwidth. This thesis bridges these two topics, and proposes to solve challenges in data storage using a variety of coding techniques, so that storage becomes faster, more affordable, and more reliable.

We consider the system level and study the integration of RAID schemes and distributed storage. Erasure-correcting codes are the basis of the ubiquitous RAID schemes for storage systems, where disks correspond to symbols in the code and are located in a (distributed) network. Specifically, RAID schemes are based on MDS (maximum distance separable) array codes that enable optimal storage and efficient encoding and decoding algorithms. With r redundancy symbols an MDS code can sustain r erasures. For example, consider an MDS code that can correct two erasures. It is clear that when two symbols are erased, one needs to access and transmit all the remaining information to rebuild the erasures. However, an interesting and practical question is: What is the smallest fraction of information that one needs to access and transmit in order to correct a single erasure? In Part I we will show that the lower bound of 1/2 is achievable and that the result can be generalized to codes with arbitrary number of parities and optimal rebuilding.

We consider the device level and study coding and modulation techniques for emerging non-volatile memories such as flash memory. In particular, rank modulation is a novel data representation scheme proposed by Jiang et al. for multi-level flash memory cells, in which a set of n cells stores information in the permutation induced by the different charge levels of the individual cells. It eliminates the need for discrete cell levels, as well as overshoot errors, when programming cells. In order to decrease the decoding complexity, we propose two variations of this scheme in Part II: bounded rank modulation where only small sliding windows of cells are sorted to generated permutations, and partial rank modulation where only part of the n cells are used to represent data. We study limits on the capacity of bounded rank modulation and propose encoding and decoding algorithms. We show that overlaps between windows will increase capacity. We present Gray codes spanning all possible partial-rank states and using only ``push-to-the-top'' operations. These Gray codes turn out to solve an open combinatorial problem called universal cycle, which is a sequence of integers generating all possible partial permutations.

Relay lens-free birefringence-customized stackable beam-steering modules for optical interconnects

A previously suggested birefringence-customized modular optical interconnect technique is extended for lens-free relay operation. Various lens-free relay imaging models are developed. We claim that the lens-free relay system is important in simplifying an optical interconnect system whenever the imaging conditions permit. To verify the validity of various proposed concepts, we experimentally implemented some 8 x 8 optical permutation modules. High-power efficiency and low channel cross talk were experimentally observed. In general, the larger the channel spacing, the less the cross talk. A quantitative cross-talk measurement of the lens-free relay system shows that, for a fixed channel width of 0.5 mm and channel spacings of 0.5, 1, and 2 mm, a less than -20-dB cross-talk performance can be guaranteed for lens-free relay distances of 40, 280, and 430 mm, respectively. (C) 1998 Optical Society of America.

Optical two-dimensional SW-banyan network: Optical implementation, routing control, and determination of permissible permutations

A 2-D SW-banyan network is introduced by properly folding the 1-D SW-banyan network, and its corresponding optical setup is proposed by means of polarizing beamsplitters and 2-D phase spatial light modulators. Then, based on the characteristics and the proposed optical setup, the control for the routing path between any source-destination pair is given, and the method to determine whether a given permutation is permissible or not is discussed. Because the proposed optical setup consists of only optical polarization elements, it is compact in structure, its corresponding energy loss and crosstalk are low, and its corresponding available number of channels is high. (C) 1996 Society of Photo-Optical Instrumentation Engineers.

On the set of eigenvalues of a class of equimodular matrices

The structure of the set ϐ(A) of all eigenvalues of all complex matrices (elementwise) equimodular with a given n x n non-negative matrix A is studied. The problem was suggested by O. Taussky and some aspects have been studied by R. S. Varga and B.W. Levinger.

If every matrix equimodular with A is non-singular, then A is called regular. A new proof of the P. Camion-A.J. Hoffman characterization of regular matrices is given.

The set ϐ(A) consists of m ≤ n closed annuli centered at the origin. Each gap, ɤ, in this set can be associated with a class of regular matrices with a (unique) permutation, π(ɤ). The association depends on both the combinatorial structure of A and the size of the a_ii. Let A be associated with the set of r permutations, π₁, π₂,…, π_r, where each gap in ϐ(A) is associated with one of the π_k. Then r ≤ n, even when the complement of ϐ(A) has n+1 components. Further, if π(ɤ) is the identity, the real boundary points of ɤ are eigenvalues of real matrices equimodular with A. In particular, if A is essentially diagonally dominant, every real boundary point of ϐ(A) is an eigenvalues of a real matrix equimodular with A.

Several conjectures based on these results are made which if verified would constitute an extension of the Perron-Frobenius Theorem, and an algebraic method is introduced which unites the study of regular matrices with that of ϐ(A).

Normal structures and automorphism groups of t-designs

Combinatorial configurations known as t-designs are studied. These are pairs ˂B, ∏˃, where each element of B is a k-subset of ∏, and each t-design occurs in exactly λ elements of B, for some fixed integers k and λ. A theory of internal structure of t-designs is developed, and it is shown that any t-design can be decomposed in a natural fashion into a sequence of “simple” subdesigns. The theory is quite similar to the analysis of a group with respect to its normal subgroups, quotient groups, and homomorphisms. The analogous concepts of normal subdesigns, quotient designs, and design homomorphisms are all defined and used.

This structure theory is then applied to the class of t-designs whose automorphism groups are transitive on sets of t points. It is shown that if G is a permutation group transitive on sets of t letters and ф is any set of letters, then images of ф under G form a t-design whose parameters may be calculated from the group G. Such groups are discussed, especially for the case t = 2, and the normal structure of such designs is considered. Theorem 2.2.12 gives necessary and sufficient conditions for a t-design to be simple, purely in terms of the automorphism group of the design. Some constructions are given.

Finally, 2-designs with k = 3 and λ = 2 are considered in detail. These designs are first considered in general, with examples illustrating some of the configurations which can arise. Then an attempt is made to classify all such designs with an automorphism group transitive on pairs of points. Many cases are eliminated of reduced to combinations of Steiner triple systems. In the remaining cases, the simple designs are determined to consist of one infinite class and one exceptional case.

Application of Entropy and Fractal Dimension Analyses to the Pattern Recognition of Contaminated Fish Responses in Aquaculture

The objective of the work was to develop a non-invasive methodology for image acquisition, processing and nonlinear trajectory analysis of the collective fish response to a stochastic event. Object detection and motion estimation were performed by an optical flow algorithm in order to detect moving fish and simultaneously eliminate background, noise and artifacts. The Entropy and the Fractal Dimension (FD) of the trajectory followed by the centroids of the groups of fish were calculated using Shannon and permutation Entropy and the Katz, Higuchi and Katz-Castiglioni's FD algorithms respectively. The methodology was tested on three case groups of European sea bass (Dicentrarchus labrax), two of which were similar (C1 control and C2 tagged fish) and very different from the third (C3, tagged fish submerged in methylmercury contaminated water). The results indicate that Shannon entropy and Katz-Castiglioni were the most sensitive algorithms and proved to be promising tools for the non-invasive identification and quantification of differences in fish responses. In conclusion, we believe that this methodology has the potential to be embedded in online/real time architecture for contaminant monitoring programs in the aquaculture industry.

Estruturas fundamentais dos gêneros literários: narração e descrição, regularidade e irregularidade

Toda a reflexão sobre os gêneros literários desenvolvida ao longo da história do Ocidente acaba, de uma maneira ou outra, por afirmar uma dualidade de procedimentos compositivos, os quais estruturam os mais diversos gêneros literários historicamente constituídos: os procedimentos de narrar e descrever. Enquanto o primeiro incorpora o aspecto temporal da experiência humana, com ênfase na causalidade, hierarquia, universalidade e subordinação de partes a um todo, o segundo incorpora o aspecto espacial da experiência humana, com ênfase na aleatoriedade, liberdade, particularidade e permutação coordenativa de partes integrantes de um todo. Narração e descrição, com qualidades estilísticas bem particulares, veiculam visões de mundo antitéticas, porém complementares. Já que dizem respeito mais ao sentido último das obras, podem ser chamadas de princípios morfossemânticos de construção das obras literárias. Todavia, ocorre que esses princípios não abarcam todos os aspectos diferenciadores das obras. Do mesmo modo como se dá ao nível do sentido último do texto, a dualidade universal/particular se reproduz na própria materialidade da linguagem, instaurando a diferença entre estruturas de elocução regular e estruturas de elocução irregular. Esse, afinal, é o cerne da diferenciação canônica entre obra lírica e obra épica, a primeira mais irregular, a segunda mais regular. Trata-se, aí, dos princípios morfológicos de construção das obras literárias. As duas ordens de princípios convergem, de maneira que a narração está para a regularidade do mesmo modo como a descrição está para a irregularidade

Prediction of mesophotic coral distributions in the Au‘au Channel, Hawaii

The primary objective of this study was to predict the distribution of mesophotic hard corals in the Au‘au Channel in the Main Hawaiian Islands (MHI). Mesophotic hard corals are light-dependent corals adapted to the low light conditions at approximately 30 to 150 m in depth. Several physical factors potentially influence their spatial distribution, including aragonite saturation, alkalinity, pH, currents, water temperature, hard substrate availability and the availability of light at depth. Mesophotic corals and mesophotic coral ecosystems (MCEs) have increasingly been the subject of scientific study because they are being threatened by a growing number of anthropogenic stressors. They are the focus of this spatial modeling effort because the Hawaiian Islands Humpback Whale National Marine Sanctuary (HIHWNMS) is exploring the expansion of its scope—beyond the protection of the North Pacific Humpback Whale (Megaptera novaeangliae)—to include the conservation and management of these ecosystem components. The present study helps to address this need by examining the distribution of mesophotic corals in the Au‘au Channel region. This area is located between the islands of Maui, Lanai, Molokai and Kahoolawe, and includes parts of the Kealaikahiki, Alalākeiki and Kalohi Channels. It is unique, not only in terms of its geology, but also in terms of its physical oceanography and local weather patterns. Several physical conditions make it an ideal place for mesophotic hard corals, including consistently good water quality and clarity because it is flushed by tidal currents semi-diurnally; it has low amounts of rainfall and sediment run-off from the nearby land; and it is largely protected from seasonally strong wind and wave energy. Combined, these oceanographic and weather conditions create patches of comparatively warm, calm, clear waters that remain relatively stable through time. Freely available Maximum Entropy modeling software (MaxEnt 3.3.3e) was used to create four separate maps of predicted habitat suitability for: (1) all mesophotic hard corals combined, (2) Leptoseris, (3) Montipora and (4) Porites genera. MaxEnt works by analyzing the distribution of environmental variables where species are present, so it can find other areas that meet all of the same environmental constraints. Several steps (Figure 0.1) were required to produce and validate four ensemble predictive models (i.e., models with 10 replicates each). Approximately 2,000 georeferenced records containing information about mesophotic coral occurrence and 34 environmental predictors describing the seafloor’s depth, vertical structure, available light, surface temperature, currents and distance from shoreline at three spatial scales were used to train MaxEnt. Fifty percent of the 1,989 records were randomly chosen and set aside to assess each model replicate’s performance using Receiver Operating Characteristic (ROC), Area Under the Curve (AUC) values. An additional 1,646 records were also randomly chosen and set aside to independently assess the predictive accuracy of the four ensemble models. Suitability thresholds for these models (denoting where corals were predicted to be present/absent) were chosen by finding where the maximum number of correctly predicted presence and absence records intersected on each ROC curve. Permutation importance and jackknife analysis were used to quantify the contribution of each environmental variable to the four ensemble models.

An examination of spatial and temporal genetic variation in walleye pollock (Theragra chalcogramma) using allozyme, mitochondrial DNA, and microsatellite data

We used allozyme, microsatellite, and mitochondrial DNA (mtDNA) data to test for spatial and interannual genetic diversity in wall-eye pollock (Theragra chalcogramma) from six spawning aggregations representing three geographic regions: Gulf of Alaska, eastern Bering Sea, and eastern Kamchatka. Interpopulation genetic diversity was evident primarily from the mtDNA and two allozyme loci (SOD-2*, MPI*). Permutation tests ˆindicated that FST values for most allozyme and microsatellite loci were not significantly greater than zero. The microsatellite results suggested that high locus polymorphism may not be a reliable indicator of power for detecting population differentiation in walleye pollock. The fact that mtDNA revealed population structure and most nuclear loci did not suggests that the effective size of most walleye pollock populations is large (genetic drift is weak) and migration is a relatively strong homogenizing force. The allozymes and mtDNA provided mostly concordant estimates of patterns of spatial genetic variation. These data showed significant genetic variation between North American and Asian populations. In addition, two spawning aggregations in the Gulf of Alaska, in Prince William Sound, and off Middleton Island, appeared genetically distinct from walleye pollock spawning in the Shelikof Strait and may merit management as a distinct stock. Finally, we found evidence of interannual genetic variation in two of three North American spawning aggregations, similar in magnitude to the spatial variation among North American walleye pol-lock. We suggest that interannual genetic variation in walleye pollock may be indicative of one or more of the following factors: highly variable reproductive success, adult philopatry, source-sink metapopulation structure, and intraannual variation (days) in spawning timing among genetically distinct but spatially identical spawning aggregates.

Different protein tyrosine phosphatase superfamilies resulting from different gene reading frames

Protein tyrosine phosphatases (PTPs) are comprised of two superfamilies, the phosphatase I superfamily containing a single low-molecular-weight PTP (lmwPTP) family and the phosphatase II superfamily including both the higher-molecular-weight PTP (hmwPTP) and the dual-specificity phosphatase (DSP) families. The phosphatase I and H superfamilies are often considered to be the result of convergent evolution. The PTP sequence and structure analyses indicate that lmwPTPs, hmwPTPs, and DSPs share similar structures, functions, and a common signature motif, although they have low sequence identities and a different order of active sites in sequence or a circular permutation. The results of this work suggest that lmwPTPs and hmwPTPs/DSPs are remotely related in evolution. The earliest ancestral gene of PTPs could be from a short fragment containing about 90similar to120 nucleotides or 30similar to40 residues; however, a probable full PTP ancestral gene contained one transcript unit with two lmwPTP genes. All three PTP families may have resulted from a common ancestral gene by a series of duplications, fusions, and circular permutations. The circular permutation in PTPs is caused by a reading frame difference, which is similar to that in DNA methyltransferases. Nevertheless, the evolutionary mechanism of circular permutation in PTP genes seems to be more complicated than that in DNA methyltransferase genes. Both mechanisms in PTPs and DNA methyltransferases can be used to explain how some protein families and superfamilies came to be formed by circular permutations during molecular evolution.

On representing chemical environments

We review some recently published methods to represent atomic neighbourhood environments, and analyse their relative merits in terms of their faithfulness and suitability for fitting potential energy surfaces. The crucial properties that such representations (sometimes called descriptors) must have are differentiability with respect to moving the atoms, and invariance to the basic symmetries of physics: rotation, reflection, translation, and permutation of atoms of the same species. We demonstrate that certain widely used descriptors that initially look quite different are specific cases of a general approach, in which a finite set of basis functions with increasing angular wave numbers are used to expand the atomic neighbourhood density function. Using the example system of small clusters, we quantitatively show that this expansion needs to be carried to higher and higher wave numbers as the number of neighbours increases in order to obtain a faithful representation, and that variants of the descriptors converge at very different rates. We also propose an altogether new approach, called Smooth Overlap of Atomic Positions (SOAP), that sidesteps these difficulties by directly defining the similarity between any two neighbourhood environments, and show that it is still closely connected to the invariant descriptors. We test the performance of the various representations by fitting models to the potential energy surface of small silicon clusters and the bulk crystal.

Spatial distribution of benthic algae in the Gangqu River, Shangrila, China

This study consisted of sampling benthic algae at 32 sites in the Gangqu River, an important upstream tributary of the Yangtze River. Our aims were to characterize the benthic algae communities and relationships with environmental variables. Among the 162 taxa observed, Achnanthes linearis and Achnanthes lanceolata var. elliptica were the dominant species (17.10% and 14.30% of the total relative abundance, respectively). Major gradients and principal patterns of variation within the environmental variables were detected by principal component analysis (PCA). Then non-metric multidimensional scaling (NMS) divided all the sites into three groups, which were validated by multi-response permutation procedures (MRPP). Canonical correspondence analysis (CCA) indicated that three environmental variables (TN, TDS, and TP) significantly affected the distribution of benthic algae. Weighted averaging regression and cross-calibration produced strong models for predicting TN and TDS concentration, which enabled selection of algae taxa as potentially sensitive indicators of certain TN and TDS levels: for TN, Achnanthes lanceolata, Achnanthes lanceolata var. elliptica, and Cymbella ventricosa var. semicircularis; for TDS, Cocconeis placentula, Cymbella alpina var. minuta, and Fragilaria virescens. The present study represents an early step in establishing baseline conditions. Further monitoring is suggested to gain a better understanding of this region.

When Does a Polynomial Over a Finite Field Permute the Elements of the Field?

We present a class of indecomposable polynomials of non prime-power degree over the finite field of two elements which are permutation polynomials on infinitely many finite extensions of the field. The associated geometric monodromy groups are the simple ...

一种可并行的消息认证码

提出并分析了一种确定的、可并行的消息认证码--DPMAC(deterministic parallelizable message authentication code).它基于分组长度为128-bit的分组密码来构造.使用一个密钥,可以处理任意长度的消息.在底层分组密码是伪随机置换的假设下,使用Game-Playing技术量化了攻击者成功伪造的概率,从而证明了其安全性.

一种可证明安全的消息认证码

消息认证码是保证消息完整性的重要工具,它广泛应用于各种安全系统中.随着可证明安全理论的逐渐成熟,具备可证明安全的消息认证码无疑成为人们的首选.本文基于XOR MAC和PMAC的构造方法,使用分组密码构造了一种确定性、可并行的消息认证码-DXOR MAC(Deterministic XOR MAC).在底层分组密码是伪随机置换的假设下,本文使用Game-Playing技术量化了攻击者成功伪造的概率,从而证明了其安全性.