Ph.D Thesis

Ph.D StudentSharov Artyom
SubjectCoding for New Applications in Storage Media
DepartmentDepartment of Computer Science
Supervisor PROF. Ronny Roth
Full Thesis textFull thesis text - English Version


Conventional magnetic recording media are composed of magnetizable units called grains, random in size and shape. Information is stored on such media through a mechanism that sets the magnetic polarities of grains to one of two possible types. If the boundaries of the grains were known to the write and readback apparatuses, then, theoretically, it would be possible to attain the storage capacity of one bit per grain. In practice, this is still impossible, since the existing technology is incapable of setting polarities of regions as small as a single grain. Instead, we need to partition the medium into a lattice of equally shaped cells and then write on a per-cell basis. A cell is larger than a grain, thus writing a bit into a cell boils down to uniformly magnetizing all the grains inside it, thereby resulting in the recording rate of one bit per cell.

Recently, Wood, Williams, Kav̆cíc, and Miles proposed an approach, which enables magnetizing areas commensurate with the size of grains, implying the feasibility of sharing the same grain between adjacent cells and effectively creating a different type of medium, where the grain polarity is determined by the last bit written into any cell sharing that grain. To simplify the original 2-D problem, the new medium can be modeled as a 1-D array of cells, over which a granular structure is imposed by grouping adjacent cells into grains of arbitrary lengths. Reading is considered reliable, whereas writing within a cell overwrites all the cells pertaining to the same grain and introduces substitution errors. This combinatorial model was considered by Mazumdar, Barg and Kashyap, who named the codes correcting such errors grain-correcting codes. A variation of that model allowing overlaps of substitution errors can be found in shingled writing on bit-patterned media.

The same medium can also be modeled probabilistically by assuming that errors occur with a prescribed probability distribution only in cells whose value differs from that of the previously written cell. This introduces a channel whose output can differ from the corresponding input due to the adversary distortions of the medium. We refer to a channel which describes the behavior of granular media with overlaps as a generalized Ising channel. Similarly, one can define a generalized Ising channel with feedback.

In this work, we present improved lower and upper bounds on the size and asymptotic growth rate of grain-correcting codes with and without overlapping error patterns. We also give explicit interesting constructions of grain-correcting codes correcting small or large number of errors. We then switch to the detection of grain errors and provide lower and upper bounds on the minimum redundancy of codes detecting any number of grain errors. Finally, we give tight bounds on the capacity of generalized Ising channels. For Ising channels with feedback corresponding to a range of values of the channel error probability, we establish a closed-form expression for their capacity; for channels corresponding to the remaining values of the error probability, we find tight lower bounds on their capacity.