LABORATORY 3
Laboratory of Data Analysis,
Error Correction Codes
and
Cryptology
Head of Laboratory – Dr.Sci.
(Technology), Prof. Victor Zyablov
Tel.: (095) 299-50-96; E-mail: zyablov@iitp.ru
The leading researchers of the laboratory include:
|
Dr.Sci. (Techn.) |
V. Gitis |
Dr. |
S. Pirogov |
|
Dr.Sci. (Math.) |
V. Sorokin |
Dr. |
V. Sidorenko |
|
Dr. |
V. Aphanasiev |
Dr. |
I. Stenina |
|
Dr. |
A. Barg |
Dr. |
A. Trushkin |
|
Dr. |
S. Bezrucov |
Dr. |
D. Zigangirov |
|
Dr. |
A. Davydov |
|
A. Chmora |
|
Dr. |
A. Genkin |
|
A. Vainshtok |
|
Dr. |
E. Jurkov |
|
E. Vashenko |
|
Dr. |
V. Pereverzev-Orlov |
|
M. Vitushko |
|
Dr. |
E. Petrova |
|
|
Directions of activity:
·
error control codes and information transmission;
·
geoinformation technologies and systems;
·
partner system design;
·
theory of the speech signal.
MAIN RESULTS
Error
Control Codes and Information Transmission
The following
problems are under consideration:
·
constructions, decoding and bounds for convolutional and block codes;
·
concatened codes;
·
combinatorial problems in vector spaces, covering codes, designs;
·
arcs, caps, and saturating sets in projective geometries over finite
fields;
·
graph theory;
·
arithmetic of finite fields.
Distinct
variants of woven convolutional codes were developed and researched. A
construction of space-temporal codes on the base woven convolutional codes is developed
and investigated. By the simulating method it is shown that such construction
is more effective than other known ones when there are some transmitting and
receiving antennas.
Jointly with
Lund University (Sweden) a subclass of woven convolutional codes using cyclic
closed convolutional codes as one of components was created and analysed. Such
codes are useful since for many concatened systems there is necessity to decide
about subblock before than whole block is received. Examples of such systems
are systems with jumping frequencies and systems on the base OFDM. Results of
these joint researches are as follows:
1.
Constructions of woven convolutional codes for which either inner or outer
codes are cyclic closed convolutional codes are developed.
2. It is shown
that in the case when cyclic closed convolutional code is choosen as one of
code component then constructions on the base inner convolutional codes and on
the base outer convolutional codes coincide with each other and their generating
matrix is defined as Kronecker production of generating matrices of code components.
3. It is shown
that free code distance of woven convolutional code using cyclic closed
convolutional codes as one of components is a product of distances of subcodes.
4. Estimates of
active distances of woven convolutional codes are obtained.
The developed
class of woven convolutional code using cyclic closed convolutional codes as
one of components is useful for new communication systems, for example, for satellite
communication systems, for mobile radio systems, for without conductors
computer communication systems. These codes have small decoding complexity and
good characteristics for distinct noises.
Jointly with
Ulm University (Germany) a construction of subclass of woven convolutional
codes with unequal error protection of information symbols was created and
analysed with using simulating. It is shown that the unequal symbol protection
can be implemented for iterative decoding of woven convolutional codes.
Asymptotic estimates of the error exponent for woven convolutional codes with
unequal error protection are obtained. It is shown that if a fraction of more
protected symbols is relatively small then the protect of the rest of
information symbols is not changed in practice.
Learning of the coded-modulation has been continuated during the last
year. The main properties of learned coded QAM structures were phase invariance
and code optimization with low redundancy.
Presented a family of linear binary codes with exponentially many
codewords of minimum weight, thereby disproving a conjecture of G. Kalai and N.
Linial. Concatenated codes with fixed inner code and random outer code are
investigated. The relations between different problem statements for digital fingerprinting
are established. Presented explicit sequences of fingerprinting codes with a
polynomial decoding procedure. Derived general estimates of the distance
distribution of binary codes with a given value of the code rate of distance.
Derived bounds on the error/erasure rate of codes on the sphere in R^n under a
Forney-type incomplete decoding. Improved the known estimates in the
corresponding problem for binary codes in the Hamming space. Studied some
related problems. Error exponents of expander codes are researched, for
example, for code rates close to channel capacity. Derived exact values of the
error exponent for a typical code from Shannon's ensemble of random binary
codes.
In graph theory the following problems are considered: edge isoperimetric
problems on graphs, a hypergraph approach to the identifying parent property
for the case of multiple parents, embedding complete trees into the hypercube,
spanning subgraphs of the n-cube, k-partitioning of graphs and hypergraphs, a
new approach to Macaulay posets, a local-global principle for
vertex-isoperimetric problems.
New constructions of covering codes obtaining new codes from starting
ones was proposed and investigated. New linear and nonlinear covering codes and
an infinite families of those are obtained by constructions proposed. Derived
better estimates of the covering radius of linear codes with a known dual
distance.
A computer search in finite projective planes PG(2,q) for the spectrum
of possible sizes k of complete k-arcs is performed. New upper bounds on the
smallest size of a complete arc are obtained for q<821. New lower bounds on
the second greater size of a complete arc are got for many values q. Besides,
many new sizes of a complete arcs are obtained for 29<q<169. Minimal
saturating sets in projective spaces PG(n,q) are investigated. Estimations and
exact values of some extremal parameters are obtained. A concept of saturating
density is introduced. It allows to obtain new lower bound for the smallest
minimal saturating set. A number of exhaustive results for small q are
obtained. Many new small 1-saturating sets in PG(2,q), q<557 are constructed
by computer. A number exact results are obtained for 2-saturating sets.
Finite field towers GF(q^p^n) are researched for the case when prime p
is a factor of (q-1) and there are no other constraints on p and q. Under this
condition irreducible binomials are used for recursive extension of finite
fields. An infinite sequence of irreducible binomials, new effective algorithms
for fast multiplication and inversion, and finite and asymptotic estimates of
arithmetic complexity are obtained. Estimates of arithmetic complexity obtained
are similar to the Schonhage-Strassen estimate for integers.
During 2001 laboratory was cooperated with universities of Germany,
Sweden and Italy. The main topics of the cooperation were continuation of many
years investigations in communication problems and combinatorial problems in
vector spaces. With Ulm University (Germany) woven convolutional codes with
unequal error protection was investigated. With University of Lund (Sweden)
woven convolutional codes using cyclic closed convolutional codes as one of
components was created and analysed. These investigations were supported by
Royal Academy of Sweden. With Perugia University (Italy) arcs, caps, and
saturating sets in projective geometries over finite fields are studied.
GRANTS FROM:
·
Russian Basic
Research Foundation (99-01-00840): "Directed graphs in decoding problem of linear
codes".
·
Geoinformation technology of new
generation is under developing. Fundamental
principles of the technology are remote access to geographical information
(GI), high interactivity of GI analysis, intuitive understandable interface and
spatio-temporal data mining build in tools.
The
fundamental principles of geoinformation technology are realized in the network
analytical GIS GeoProcessotof and COMPASS, problem domains of which are
analysis and forecasting of natural and social processes and phenomena. Both
GISs are designed in Java 1.1 in client-server architecture
(http://www.iitp.ru/projects/geo, http://borneo.gmd.de/and/geoprocessor).
GIS GeoProcessor
is intended for publication and complex analysis of spatio-temporal characteristics of geological
environment and for solving of
forecasting and zonation problems in Earth sciences (natural hazard assessment,
mineral and oil/gas deposits exploration).
The system supports remote access to geographical information, interactive
cartographic analysis of grid-based, vector and point data, spatial data
mining. The system helps to evaluate the environment properties on the base of
principle of analogy using the
methods of multidimensional plausible reasoning: method of similarity on a
precedent set, method of similarity on expert fuzzy logic knowledge, method of
membership function for two classes, method of nonparametric regression.
GIS COMPASS II
(Cartography Online Modeling, Presentation and Analysis
System) supports analysis of vector GI. Friendly and interactive interface for
multilayer vector GI cartographic representation and intuitive understandable
tools for spatio-temporal data mining based on interactive analysis of complex
properties of geographical objects make the system available for a wide range
of the Internet users (non-professionals and specialists). Problem domains of GIS COMPASS are economy, sociology,
demography, ecology, policy, marketing research, and management control.
Demonstration
databases, which contains geological, geophysical, seismo-tectonic, social,
economic and demographic information have been created. The total volume of the
data is about 35МБ. The databases are accessible in site http://www.iitp.ru/projects/geo
for interactive cartographical exploration and analysis with the help of GISs
the GeoProcessor and COMPASS.
The
data base of geological and geophysical information in the format of GIS
GeoProcessor includes the following regions: Central Europe (46о-50о
n. and 6о-15о e.), Central Greece (36о-39.5
о n. and 20о-24.2о e.), S-E Bulgaria, Kresna (41.3о-42.7о
n. and 22.3о-24.1о e.), Turkey (35о-43о
n. And 25о-47о e.), Northern Caucasus (41.6о –
45.6о n. and with 39.6о-45.6о e.) and N-E
China (37о-42о n. and with 111о-120о e.).
Database contains the digital models of topography, geophysical fields, geological
faults, catalogues of earthquakes and topographical elements.
The
database for GIS COMPASS contains examples of social and economic information
on Russian Federation and World Countries, as well as an example of census data
on region of Manchester.
The
databases were used in research on efficiency of GISs GeoProcessor and COMPASS,
as well as remote access to the seismo-tectonic data analysis for the partners
of the joint international projects. The experimental results confirm
efficiency GISs the GeoProcessor and COMPASS.
It
allows to offer free of charge dissemination of GISs the GeoProcessor and
COMPASS to publish and analyze geographical information for scientific and educational
centers of Russia, including the sites of the appropriate grants RFBR the holders.
Analysis of the
relationships between seismicity and tidal forces is realized on the basis of
USGS/NEIC seismic data. On calculating of tidal vector we take into account
only component of tidal force conditioned by the Moon. We examine six
attributes of tidal vector: vertical, meridianal, latitudinal components,
module of horizontal tidal force, module of tidal vector and amplitude of
diurnal fluctuation of tidal force. The weak correlations between magnitude of
earthquakes and meridional component of tidal force are discovered at the
global level and under partitioning
surface of the Earth on meridianal sectors. For the last case the maximum correlation
(0.22о) falls at 35о. W. There are no correlations between the
magnitude and the remaining five tidal attributes. The relationships between
frequency of earthquakes and amplitude of diurnal fluctuation of tidal force
are discovered both at the global level and within latitudinal bands of the
Earth. The relationships between frequency of earthquakes and the five
remaining tidal attributes are not found.
Within the
framework of the instrumental environment MATLAB a software package are
developed for revelation of relationships between frequency of earthquakes and
tidal attributes of tidal force. The software package contains computing and cartographic
sections. The first section supports computation of components of tidal force
and testing of statistical hypothesis concerning relationships between
seismicity and attributes of tidal force. The second section supports creation
of maps of seismic activity prevalence and helps to reveal the areas, which are
seismic sensitive to terrestrial tides. With help of this software we found a
number of areas, which are the most seismic sensitive to terrestrial tides. All
the areas belong to the Earth seismic belts; most of areas connect with oceanic
structures.
International
cooperation. Cooperation within the
framework of the 5FP IST program, under the project "Spatial mining for
Data of Public Interest", acronym SPIN!, contract IST-1999-10536 was
proceed. The following countries participate at the Project: Germany, Italy,
Great Britain and Netherlands. Very close problems investigated in scope of the
Agreement on scientific and technical cooperation with of German
National Research Center for Information Technology (GMD) GMD (new name is Fraunhofer Gesellschaft) "Spatial-Temporary Data Mining Information Technology
for Environmental and Human Dimension Applications".
Some methods of GIS
GeoProcessor and GIS Descartes (Germany) were integrated, the new methods of
the spatio-temporal analysis of grid-based and vector data were developed, the
database of geographical, geophysical, seismological and infrastructure data on
the Turkey test area was collected. The methods are realized in jointly created
new WWW analytical GIS.
The agreement on scientific
and technical cooperation with Institute of Astronomy and Geodesy (Madrid
university Complutense) "Intelligent Data Analysis of Lanzarote Island by
Advanced Geoinformation Technology" was made
in November 2001. The inspection of basic data is begun.
The work with Institute of
the Earthquake Prediction and Analysis of Chinese State Seismological Bureau
(CSB) was conducted within the framework of the agreement on scientific and
technical cooperation between RAS and CSB (together with UIPE RAS) “Study and
physical interpretation of spatio-temporal variations of earthquake precursors
in the North-East China”. The joint research on spatio-temporal analysis of
seismicity of North-East China was executed, the data base on North-Eeast China
was created, the data were combined in GeoProcessor database and were represented
at http://www.iitp.ru/projects/geo. The local versions of systems the
GeoProcessor and COMPASS 1 as well as updated GIS GeoTime were given to the
Chinese colleagues. The results of GIS GeoTime application the Chinese
earthquake prediction from the Chinese party as well as new unique data of
seismological and geophysical monitoring for the North-East China were
accepted. The cooperation will be continued.
The research
results were reported on the conferences and workshops in Germany, Italy,
Netherlands and Ukraine. The systems GeoProcessor and COMPASS 2 were presented
with the support of RF Ministry of industry, science and technology at
international exhibitions on information technologies CeBit’2001 (Germany) and
Simo’2001 (Spain).
GRANTS FROM:
·
Russian Basic
Research Foundation (No. 00-07-90100): "Network geoinformation systems
for presentation and analysis of spatio-temporal information referring to Earth
Sciences and human dimension".
·
Russian Basic
Research Foundation (No. 99-07-90326): "World online data
center".
·
Russian Basic
Research Foundation (No. 99-05-64218): "Spatial-temporal
distributions of the ruptures and seismic sources in the Earth crust and theirs
connection with the peculiarities of orbital and rotative motions of the Earth
(by using of electronic catalogs) ".
·
Ministry of
science and technology of Russia: "Development of an Information Technology for
Model Designing and Forecasting of the Natural and Manmade Catastrophes".
·
IST Program (EU IST – 10536): "Spatial Mining
for Data of Public Interest (SPIN!)".
The methods and
tools of designing of large knowledge bases in
medicine are under development. The methods are intended to support in the
interaction of different users and the integration of knowledge and data from
different sources. The main research problem was merging local knowledge bases
into general knowledge base. Development of the programs started that assist a
domain expert in the ascertainment of conceptual, contextual, and structural
congruence of merging bases. Next problem was producing a new local knowledge
base on the basis of some initial prototype, formed as a projection of the
existing large knowledge base on the domain of interest. The technology of such
projecting was proposed.
Within the framework of Partner System project a conception of
intelligent tutoring has been elaborated. The programs, supporting for the
multi-stage process of professional
education, are under development now.
A method of classification for medical images, represented as the
temporal sequences of frames (films), has been developed. A set of
transformations was designed to emphasize some presumably important
spatio-temporal image characteristics. The appropriate local spatial
approximation was selected to represent each film as a set of time series for
all designed characteristics. The classification rule was constructed in the
form of three-level threshold neuron-like net with the levels of spatial,
temporal and integral synthesizing. The method was effectively applied in the
task of early breast cancer diagnostics based on dynamic optical patterns.
GRANTS FROM:
·
Russian
Foundation for Basic Researches (No. 01-01-01020): "The development of knowledge management
methods for large clinical knowledge-based system".
·
Program
of Presidium of Russian Academy of Sciences "Intellectual Computer
Systems" (№ 3.4): Intelligent decision support within
the framework of the project "Partner System".
THEORY OF THE SPEECH SIGNAL
A speech
database for digits, voice dialling commands and utterances has been completed.
The speech signal was recorded for 60 speakers using 4 types of microphones and
2 type of telephone handsets. A software prototype of a speech recognition
system was developed. It includes a unit of spectral-temporal analysis of the
speech signal, units of primary and articulatory detectors, segmentator and
decoder.
The role of
pharyngeal constrictors in speech production processes was described and
3-dimensional model of the vocal tract was formed on the basis magneto-resonance
measurements of the 3-dimensional vocal tract shape.
A dynamic
inverse problem with respect to motor control commands was studied for the case
of known area of the vocal tract and 3 resonance frequencies.
Publications in 2001
Articles
1. Ashikhmin A.,
Barg A., and Litsyn S. Estimates of the distance distribution of codes and
designs // IEEE Transactions on Information Theory. 2001, vol. 47, no. 3, Also
Proceedings ISIT 2001, Washington, DC, p. 111.
2. Barg A., Cohen
G., Encheva S., Kabatiansky G., and Zemor G. A hypergraph approach to the
identifying parent property: the case of multiple parents // SIAM Journal on Discrete
Mathematics. 2001, vol. 14, no. 3, pp. 423-431.
3. Barg A.,
Justesen J., and Thomessen C. Concatenated codes with fixed inner code and
random outer code // IEEE Transactions on Information Theory. 2001, vol. 47,
no. 1, pp. 361-365.
4. Barg A. and
Litsyn S. (Editors). Codes and Association Schemes. Providence: AMS, 2001.
5. Bezrukov S.L.
Embedding complete trees into the hypercube // Discrete Applying Mathematics.
2001, vol. 110, no. 2-3, pp. 101-119.
6. Davydov A.A.
New constructions of covering codes // Designs, Codes and Cryptography. 2001,
vol. 22, pp. 305-316.
7. Davydov A.A.
and Ostergard P.R.J. Recursive constructions of complete caps // Journal of
Statistic and Planning Inference. 2001, vol. 95, pp. 163-173.
8. Davydov A.A.
and Ostergard P.R.J. Linear codes with covering radius R=2,3 and codimension tR
// IEEE Transactions on Information Theory. 2001, vol. 47, pp. 416-421.
9. Freudenberger
J., Bossert M., Zyablov V.V., and Shavgulidze S. Woven codes with outer warp:
Variation, Design and Distance properties // IEEE journal on "Selected
areas in communication". 2001 (May), vol. 19, no. 6, pp. 813-824.
10. Zyablov V.V., Shavgulidze S., and
Johannesson R. On the error exponent for woven convolutional codes with inner
warp // IEEE Transactions on Information Theory. 2001, vol. 47, no.3.
11. Andrienko G.,
Andrienko N., Gitis V., and Denissovitch I. Interactive Maps for Visual
Exploration of Grid Data // International Archives of Photogrammetry and Remote
Sensing. Vol. 34, Part 4/W5, Challenges in Geospatial Analysis, Integration and
Visualization. 2001, pp. 6-8.
12. Гитис В.Г, Вайншток
А.П. Сетевые аналитические ГИС //
ГИС обозрение. 2001, № 2, c. 14-16.
13. Вайншток А.П., Гитис В.Г. Сетевые аналитические
геоинформационные технологии и системы // Proceedings of the XXVIII conference on Information Technologies in Science, Education,
Telecommunication, Business, Гурзуф, 20-30 сентября 2001, с. 100-104.
14. Витушко М.А., Гуров Н.Д., Переверзев-Орлов В.С. Синдромное
прогнозирование изменчивости // Сб. докладов 10-й Всероссийской конференции
"Математические методы распознавания образов" (ММРО-10), Звенигород,
2001, с. 28-30.
In print
1. Barg A.,
Blakley G. R., and Kabatiansky G. Digital fingerprinting codes: Problem
statements, existence, constructions // IEEE Transactions on Information Theory
(submitted). Also Proceedings ISIT 2001, Washington, DC, p. 161.
2.
Afanassiev V.B. and Davydov A.A. Finite field towers:
iterated presentation and complexity of arithmetic // Finite Fields and their
Applications (to appear).
3.
Ashikhmin A.and Barg A. Bounds on the covering radius of
linear codes // Designs, Codes and Cryptography (to appear).
4.
Ashikhmin A., Barg
A., and Vladuts S. Linear codes with exponentially many light vectors //
Journal Combinatorial Theory, ser. A (to appear).
5. Barg A. On
error bounds for spherical and binary codes // IEEE Transactions Information
Theory (submitted). Also Proceedings ISIT 2001, Washington, DC, p. 38.
6. Barg A. and
Forney G. D. Random codes: Minimum distances and error exponents // IEEE
Transactions on Information Theory (submitted).
7. Barg A. and
Zemor G. Error exponents of expander codes (submitted).
8. Barg A. and
Zemor G. Error exponents of expander codes // IEEE Transactions on Information
Theory (to appear). Also Proceedings ISIT 2001, Washington, DC, p. 47.
9. Bezrukov S.L.,
Pfaff T., Piotrowski V.P. A new approach to Macaulay posets // Journal of
Combinatorial Theory (submitted).
10. Bezrukov S.L. and Serra O. A
local-global principle for vertex-isoperimetric problems // Discrete
Mathematics (to appear).
11. Jordan R., Host S., Bossert M.,
Johannesson R., and Zyablov V.V. Woven convolutional codes II: Decoding aspects
// IEEE Transactions on Information Theory (submitted).
12. Jordan R., Pavluchkov V., and Zyablov
V.V. Maximum slope convolutional codes // IEEE Transactions on Information
Theory (submitted).
13. Handler M.,
Johannesson R., and Zyablov V.V. On the error correcting capability of window
decoding // ISIT 2002 (submitted).
14. Handler M.,
Johannesson R., and Zyablov V.V. Boosting the error performance of suboptimal
tailbiting decoders // IEEE Transactions on Communication (submitted).
15. Хандлер М., Йоханнессон Р., Зяблов В.В. Кодер и свойства расстояний
плетеных сверточных кодов с циклически замкнутым компонентным кодом // Проблемы
передачи информации (в печати).
16. Host S., Johannesson R., and Zyablov
V.V. Woven convolutional codes I: Encoder Properties // IEEE Transactions on
Information Theory (to appear).
17. Zyablov V. and Jordan R. On woven
convolutional code with outer warp and unequal error protection // ETT
(submitted).
18. Vitushko M., Gurov N.,
Pereverzev-Orlov V. Syndrom as a method of conceptual modeling // Pattern
Recogn. and Image Anal. 2002, vol. 12, no. 2 (to be published).
19. Юрков Е.Ф. Система анализа характеристик акустического
процесса при разрушении образцов горных пород // Вулканология и сейсмология (в
печати).
20. Sorokin V.N. Some coding properties
of speech // Speech Communication Journal (submitted).
21. Leonov A.S., Sorokin V.N. Controls
in the internal model: Score reorganization and compensation // Journal of
Phonetics (submitted).