93 research outputs found
Highlights of Library Automation related documents in the INSPEC
No full textThe paper has attempted to analyse the Library Automation related records in the INSPEC (1969 to July 2004). The growth of Library Automation related literature, country of input, scattering of literature in different publication types, core journals publishing Library Automation related publications, language-wise proportion of the literature, content analysis through keywords/descriptors, availability of URLs (Universal Resource Locator) for full text articles as alternative locations were the main focus of the study. After the year 1984, the literature grows approximately linearly with a growth rate of about 600 items per year. The USA is the predominant publishing country of Library Automation related literature. Journals are the most preferred publication media, followed by Conference/Proceedings-Papers, Book-Chapters, and Reports publications. Most productive journals are: Library Hi Tech, followed by Computers in Libraries, VINE, Information Technology and Libraries, and Program. English articles constitute 91.83% of the total literature. That means the non-English articles constitute only 8.17%. The keyword analysis indicates that the key areas of Library Automation were cataloguing; academic-libraries; information-retrieval; Internet; and information-services. The most occurred URL was http://www.dlib.org/ as alternative locations in the availability notes of Library Automation related records
Capacity Computation and Coding for Input-Constrained Channels
No full textThe setting of the transmission of information over noisy, binary-input, memoryless channels is today well-understood, owing to the work of several information theorists, beginning with Claude Shannon. It is known that it is impossible to transmit information reliably over such channels at rates larger than the fundamental limit that is the capacity of the channel. Moreover, progress made in the last three decades has led to the construction of explicit, practically-implementable coding schemes that achieve rates arbitrarily close to the capacities of such channels. Now, suppose that the inputs of the memoryless channel are required to obey an additional constraint, which stems from physical limitations of the medium over which transmission or storage occurs. What then can be said about the fundamental limits of information transmission over such input-constrained channels, with and without decoder feedback? Is it possible to design good constrained coding schemes of high rate over these channels? If the channel introduces errors adversarially, instead of randomly, how much information can then be sent through, reliably? This dissertation explores answers to such questions.
We first derive computable lower bounds on the capacities of runlength limited (RLL) input-constrained memoryless channels, such as the binary symmetric and binary erasure channels (BSC and BEC, respectively), by considering random Markov input distributions that respect the constraint. These bounds unify well-known approaches in the literature, and extend them to the so-called input-driven finite-state channels (FSCs). For the special case of the BEC with a no-consecutive-ones input constraint, we discuss an iterative stochastic approximation algorithm that numerically computes achievable rates that are very close to known upper bounds on the capacity of the channel. We also derive improved analytical lower bounds, for this specific channel.
Next, we consider the special case of the -runlength limited (RLL) constraint, which mandates that any pair of successive s be separated by at least s. We design explicit coding schemes, derived from Reed-Muller (RM) codes, for transmission over binary-input memoryless symmetric (BMS) channels, whose inputs respect the constraint. In particular, we provide constructions using constrained subcodes of RM codes, analytically compute their rates, and derive converse upper bounds on the rates of the largest constrained subcodes of RM codes. We also provide a Fourier-theoretic perspective on the problem of counting arbitrarily-constrained codewords in general linear codes, which can help estimate the rates achievable by using linear codes over input-constrained BMS channels. We illustrate the utility of our method using the somewhat surprising observation that for different constraints of interest, the Fourier transforms of the indicator functions of the constraints are efficiently computable.
We then shift our attention to the setting of the -RLL input-constrained BEC in the presence of noiseless feedback from the decoder. We demonstrate a simple, labelling-based, zero-error feedback coding scheme, which we prove to be feedback capacity-achieving, and, as a by-product, obtain an explicit characterization of the feedback capacity. The feedback capacity thus computed is an upper bound on the non-feedback capacity of such a channel. Numerical comparisons made with upper bounds on the non-feedback capacity then reveal that that feedback increases the capacity of such a channel, at least for select values of .
Finally, we consider the setting of an input-constrained adversarial channel, where there is an upper bound on the number of bit-flip errors that the channel can introduce, and we seek to design codes that can be recovered with zero error. We present numerical upper bounds on the sizes of the largest such codes, via a version of Delsarte’s linear program. We observe that for different constraints of interest, our upper bounds beat the “generalized sphere packing bounds” that are the state-of-the-art.Prime Minister's Research Fellowship, Qualcomm Innovation Fellowship Indi
Estimating the Sizes of Binary Error-Correcting Constrained Codes
No full textIn this paper, we study binary constrained codes that are resilient to
bit-flip errors and erasures. In our first approach, we compute the sizes of
constrained subcodes of linear codes. Since there exist well-known linear codes
that achieve vanishing probabilities of error over the binary symmetric channel
(which causes bit-flip errors) and the binary erasure channel, constrained
subcodes of such linear codes are also resilient to random bit-flip errors and
erasures. We employ a simple identity from the Fourier analysis of Boolean
functions, which transforms the problem of counting constrained codewords of
linear codes to a question about the structure of the dual code. We illustrate
the utility of our method in providing explicit values or efficient algorithms
for our counting problem, by showing that the Fourier transform of the
indicator function of the constraint is computable, for different constraints.
Our second approach is to obtain good upper bounds, using an extension of
Delsarte's linear program (LP), on the largest sizes of constrained codes that
can correct a fixed number of combinatorial errors or erasures. We observe that
the numerical values of our LP-based upper bounds beat the generalized sphere
packing bounds of Fazeli, Vardy, and Yaakobi (2015).Comment: 35 pages + 6 pages of supplementary material, 1 figure, 6 tables,
under review at the IEEE Journal on Selected Areas in Information Theor
Linear Runlength-Limited Subcodes of Reed-Muller Codes and Coding Schemes for Input-Constrained BMS Channels
No full textIn this work, we address the question of the largest rate of linear subcodes
of Reed-Muller (RM) codes, all of whose codewords respect a runlength-limited
(RLL) constraint. Our interest is in the -RLL constraint, which
mandates that every pair of successive s be separated by at least s.
Consider any sequence of RM codes with
increasing blocklength, whose rates approach , in the limit as the
blocklength goes to infinity. We show that for any linear -RLL
subcode, , of the code , it holds that the
rate of is at most , in the limit as the
blocklength goes to infinity. We also consider scenarios where the coordinates
of the RM codes are not ordered according to the standard lexicographic
ordering, and derive rate upper bounds for linear -RLL subcodes, in
those cases as well. Next, for the setting of a -RLL
input-constrained binary memoryless symmetric (BMS) channel, we devise a new
coding scheme, based on cosets of RM codes. Again, in the limit of blocklength
going to infinity, this code outperforms any linear subcode of an RM code, in
terms of rate, for low noise regimes of the channel.Comment: 10 pages, 5 figures, accepted to the IEEE Information Theory Workshop
(ITW) 2022. This is a follow-up manuscript of the work in arXiv:2201.02035,
which was accepted to the 2022 IEEE International Symposium on Information
Theory (ISIT
Information Rates Over Multi-View Channels
No full textWe investigate the fundamental limits of reliable communication over
multi-view channels, in which the channel output is comprised of a large number
of independent noisy views of a transmitted symbol. We consider first the
setting of multi-view discrete memoryless channels and then extend our results
to general multi-view channels (using multi-letter formulas). We argue that the
channel capacity and dispersion of such multi-view channels converge
exponentially fast in the number of views to the entropy and varentropy of the
input distribution, respectively. We identify the exact rate of convergence as
the smallest Chernoff information between two conditional distributions of the
output, conditioned on unequal inputs. For the special case of the deletion
channel, we compute upper bounds on this Chernoff information. Finally, we
present a new channel model we term the Poisson approximation channel -- of
possible independent interest -- whose capacity closely approximates the
capacity of the multi-view binary symmetric channel for any fixed number of
views.Comment: 33 pages, 1 figure, submitted to the IEE
Improving the Privacy Loss Under User-Level DP Composition for Fixed Estimation Error
No full textThis paper considers the private release of statistics of several disjoint
subsets of a datasets. In particular, we consider the -user-level
differentially private release of sample means and variances of sample values
in disjoint subsets of a dataset, in a potentially sequential manner.
Traditional analysis of the privacy loss under user-level privacy due to the
composition of queries to the disjoint subsets necessitates a privacy loss
degradation by the total number of disjoint subsets. Our main contribution is
an iterative algorithm, based on suppressing user contributions, which seeks to
reduce the overall privacy loss degradation under a canonical Laplace
mechanism, while not increasing the worst estimation error among the subsets.
Important components of this analysis are our exact, analytical
characterizations of the sensitivities and the worst-case bias errors of
estimators of the sample mean and variance, which are obtained by clipping or
suppressing user contributions. We test the performance of our algorithm on
real-world and synthetic datasets and demonstrate improvements in the privacy
loss degradation factor, for fixed estimation error. We also show improvements
in the worst-case error across subsets, via a natural optimization procedure,
for fixed numbers of users contributing to each subset.Comment: 43 pages, 8 figures, to be submitted to the IEE
Dynamic rank-maximal and popular matchings
No full textWe consider the problem of matching applicants to posts where applicants have preferences over posts. Thus the input to our problem is a bipartite graph G = (A boolean OR P, E), where A denotes a set of applicants, P is a set of posts, and there are ranks on edges which denote the preferences of applicants over posts. A matching M in G is called rank-maximal if it matches the maximum number of applicants to their rank 1 posts, subject to this the maximum number of applicants to their rank 2 posts, and so on. We consider this problem in a dynamic setting, where vertices and edges can be added and deleted at any point. Let n and m be the number of vertices and edges in an instance G, and r be the maximum rank used by any rank-maximal matching in G. We give a simple O(r (m + n))-time algorithm to update an existing rank-maximal matching under each of these changes. When r = o(n), this is faster than recomputing a rank-maximal matching completely using a known algorithm like that of Irving et al. (ACM Trans Algorithms 2(4): 602-610, 2006), which takes time O(min((r + n, r root n)m). Our algorithm can also be used for maintaining a popular matching in the one-sided preference model in O(m + n) time, whenever one exists
Achieving Secrecy Capacity of Minimum Storage Regenerating Codes for all Feasible (n, k, d) Parameter Values
No full text- …
