LABORATORY 3

Laboratory of Data Analysis, Error Correction Codes

and Cryptology

Head of Laboratory – Dr.Sc. (Technology), Prof. Victor Zyablov

Tel.: (095) 299-50-96; E-mail: zyablov@iitp.ru

The leading researchers of the laboratory include:

Dr.Sc. (Math.)

V. Sorokin

Dr.

E. Petrova

Dr.

V. Aphanasiev

Dr.

S. Pirogov

Dr.

A. Barg

Dr.

V. Sidorenko

Dr.

S. Bezrucov

Dr.

I. Stenina

Dr.

A. Davydov

Dr.

A. Trushkin

Dr.

A. Genkin

Dr.

D. Zigangirov

Dr.

V. Gitis

 

A. Chmora

Dr.

E. Jurkov

 

A. Vainshtok

Dr.

V. Pereverzev-Orlov

 

E. Vashenko

Directions of activity:

Error Control Codes and Information Transmission

The following problems are under consideration:

MAIN RESULTS

For general convolutional codes a family of an active distance measures is defined and lower bounds on these distances are derived. It is shown that the error correcting capability of a convolutional code is determined by the active distances.

Investigations of woven convolutional codes suggested in last years were continued. The general construction of woven codes called “twill” is considered together with two special cases, viz., woven convolutional encoders with outer and inner warp. The error exponents and decoding complexity of binary woven codes with outer and inner warp are studied. It is shown that for both constructions an error probability that is exponentially decreasing with the memory of woven codes can be achieved with a non-exponentially increasing decoding complexity. Furthermore, the error exponent for woven convolutional codes with inner warp is larger than the one for woven convolutional codes with outer warp. The asymptotic lower bounds on the active distances of the woven convolutional codes are obtained and it is shown that these distances can be bounded from below by linearly growing functions with a strictly positive slope for all rates of the concatenated codes. Woven codes with outer binary block codes and additional permutation are proposed.

An introduction to the theory of generalized concatenated codes is written. Properties of pulse position hopped CDMA systems for Impulse Radio Multiple Access implementation were investigated. Due to the theoretical results the number of users may be ten times greater than in systems with conventional approaches. An algorithm for constructing of a syndrome trellis of any linear block code was proposed. The algorithm constructs the minimal code trellis directly without building any extra vertices by utilizing the method of addressing trellis vertices in bases of respective linear spaces.

An experimental investigation of iterative decoding scheme based on a posteriori probability calculation was done for a convolutional code in a partial response channel. The investigation was oriented for application in a high-density magnetic recording channel. It was shown a very high efficiency of iterative Turbo scheme.

Investigation of general properties of rectangular codes was continued. (The class of rectangular codes includes all linear, group, and many nongroup codes). The rectangular algebra is defined. Bounds on cardinality of a basis of a rectangular code are given. It is shown that all bases of a t-rectangular code have the same cardinality. A simple algorithm is proposed to design a rectangular basis of a linear code using its generator matrix. A number of iterative decoding procedures with rectangular codes are proposed and studied. An algorithm designing the minimal trellis of the set of low weight codewords of a linear code is obtained. The algorithm computes also a rectangular basis of this set. This allows a compact storing of the set.

A new upper bound on the reliability function (exponent of the error probability of decoding for best possible codes) of the Gaussian channel is obtained. This bound is derived via a new approach proposed by A. Barg in last years, which extends the polynomial method in coding theory to bounds on various invariants of codes. It is the first conceptual advance in the problem since Shannon's works of 1959 and 1967.

Investigations on quantum error detection gives a consistent definition of the undetected error event for quantum codes and proves that there exist quantum codes for which the probability of undetected error falls exponentially with code length. New relations between polynomial invariants of linear codes and some combinatorial invariants (the reliability polynomial for linear matroids and the partition function of the Potts model) were obtained.

In graph theory the following problems are considered: edge isoperimetric problems on graphs, an equivalence in discrete extremal problems, a Kruskal-Katona theorem for the linear lattice, the congestion of n-cube layout on a rectangular grid, the theory of Macaylay posets, a local-global principle for Macaulay posets and for vertex-isoperimetric problems, k-partitioning of Hamming graphs. It is shown that the spider poset is Macaulay. New spectral lower bounds for the bisection width of graphs is obtained.

New constructions of covering codes with radius 2-4 using ideas of the projective geometry over finite fields and so called “complete sets of indicators” are proposed, a number of new infinite families of covering codes with the best known parameters are obtained. Saturating sets in small projective geometries and their connection with covering codes are considered.

Infinite sequences of binomials of the form x^p^n – c irreducible over extensions of Galois fields with arbitrary basis are constructed. It gives iterated presentations for infinite towers of extended fields with exponentially growing degree of extension and almost linear asymptotic complexity of arithmetic.

The new cryptographic protocol for mutual authentication and secure messaging has been proposed. The protocol is based on idea of one-time passwords (realeased and described by Bellcore) and provides high level of robustness to replay and interleaving attacks. The protocol is free on many usual disadvantages and is under patenting in US now.

During 1999 laboratory was cooperated with universities of Germany, Sweden and Finland. 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) problems of coded modulation, capacity and performances of channel for mobile communication and also problems of rectangular codes theory were considered. The work was supported by Deutsche Forschungs Gemeinschaft. Using part of the obtained results connected with rectangular codes a PhD degree was obtained by J. Maucher (Germany). Concatenated constructions based on conventional convolutional codes were investigated with University of Lund (Sweden). These investigations was supported by Royal Academy of Sweden. Covering codes over arbitrary finite fields and their connection with saturating sets in projective geometry were considered with Helsinki University of Technology (Finland). These works was supported by Academy of Finland. Some members of the laboratory are involved in joint research with the Research Center of the Bell Labs (USA).

GRANTS FROM:

 

Geoinformation Technologies and Systems

Important theoretical and applied results on geoinformation problem were achieved. The technology of information modeling of spatial-temporary processes and phenomena occurring in the geological environment is developed. Online geoinformation systems are developed.

The information model describes phenomenon under studying by computer realized formalisms (knowledge and databases, algorithms). The information model includes the following components: structured data and formalized knowledge, the features processed from raw geological and geophysical data, the versions of forecast function (a formal relationship between predicted values and the features), the space-time representation of forecast values and forecast accuracy analysis, a causal model of the phenomenon describing the derived formalisms in the problem field terms.

The elements of information model technology are realized in WWW online intelligent geoinformation system GeoProcessor (http://gis.iitp.ru/geoproc). The system is intended for publications and complex analysis of space-time characteristics of geological environment and for deciding 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 raster, vector and point data, spatial data mining and plausible inference. The main functions of the system are the following: problem formalization, formalization of the information space of the problem, preliminary data processing, generation of a set of features, solution generation, analysis and argumentation of the solution. The system helps to evaluate the environment properties on the base of principle of analogy using the methods of plausible reasoning of forecast maps on a complex of raster maps: 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, the method of certainty function for classification on monotone feature space. GeoProcessor is written on Java as client-server.

Within the framework of the project "ASPELEA" of EC Inco-Copernicus program the system GeoProcessor was used for data processing and WWW application designing for three seismic activity regions (http://gis.iitp.ru/geoproc, http://alba.jrc.it/gitis/index.html). Raw geological and geophysical data was processed and the feature raster fields were generated, relationship between feature fields and spatially distributed seismic events was investigated, also space-temporary distribution of the earthquake epicenters was investigated. The users can produce online their own experiments on represented data.

New direction of work on designing of vector Internet GIS was started. The system is intended for publishing of geographic information (GI) of such fields as economics, sociology, demography as well as for complex analysis of space-temporary referenced data and decision support in politics, business and management.

A version of the system COMPASS (Cartography Online Modeling, Presentation and Analysis System) on Java language is designed (http://gis.iitp.ru/compass). Friendly tools for GI cartographic representation and intuitive understandable tools for spatial-temporary data mining based on interactive analysis of complex properties of geographical objects make the system available for wide range of the Internet users (non-professionals and specialists). WWW applications were implemented on the base of COMPASS: Russia demographic indices http://gis.iitp.ru/undp, Marketing information system http://gis.iitp.ru/siemens. The users can produce online their own experiments on represented data.

The information technology and advanced instrumental environment GeoTime for modeling and testing hypothesizes on earthquake precursors is developed. Retrospective analysis of number of earthquakes was made, different geological and geophysical features of seismic processes were investigated, and statistical significant earthquake precursors were detected. A method of estimating the parameters of epicenter models of earthquakes precursors was developed. The methods of dynamic fields generation on earthquake catalogues are advanced. GeoTime program environment is used by scientific groups of OIPE RAS, China, Czech republic and Greece in studies on earthquake prediction and mine tremor.

New methods and software for modeling of hydrocarbons migration process and finding of deposits were designed.

International cooperation, conferences, exhibitions. Scientific cooperation within the framework of ASPELEA project of the INCO-COPERNICUS program, and on the base of bilateral agreements with the Laboratory of Applied Logic (Hungary) and the Institute of Rock Structure and Mechanics (IRSM), Academy of Sciences of the Czech Republic is continuing. A project on geoinformation problem is included to Russia-Indian scientific cooperation program. The team is involved as subcontractor to the international project “Spatial Mining for Data of Public Interest – SPIN!” (contract EU IST-10536 SPIN!).

The research results were reported on the conferences and workshops in England, Germany, Greece, and Italy. The systems GeoProcessor and Compass were presented with the support of RF Ministry of sciences at international exhibition on information technologies Simo-99 (Spain).

GRANTS FROM:

 

Partner System Group

Directions of activity

The research activities of the group aim at the development of decision support system based on the methods of knowledge and data cooperative processing (Partner system). Partner System intended for cumulating, analyzing, and delivering knowledge about some domain. It provides a user with the tools of expert knowledge conceptual modeling, knowledge acquisition from data, and knowledge integration.

Developed methods are intended on the massively incomplete, erroneous and irregularly distributed data and large knowledge bases in weakly formalized fields such as medicine. To maintain the information interchange in the form convenient and natural for the user the hierarchical threshold network is accepted as the form of knowledge representation. To induce this network structure causal relations and correlations of observations may be united. It proved to be easy conceivable by user and flexible enough to represent sophisticated models in different real-world applications.

Main results

In 1999 the basic research problem was merging local knowledge bases into general knowledge base. Methods of conceptual model coordination in united knowledge bases are in the progress.

Pattern recognition methods with the using of threshold network have been extended to apply in the tasks of continuous parameter prediction, forecasting in dynamic environment, image processing and interpretation. Results were always competing, and in many cases the best in comparison to conventional methods.

Development of intelligent decision support system for Main Military Clinical Hospital on the basis of partner system approach is started.

GRANTS FROM:

 

THEORY OF THE SPEECH SIGNAL

There were studied the types of amplitude-frequency distortions of the speech signal for various kinds of microphones, telephone receivers, different types and levels of noise in the environment and the degree of influence of chamber reverberation. A non-linear modification of the method of spectral compensation was developed for stationary noise and distortions.

Publications in 1999

  1. Affanassiev V., Technical report "Iterative receiver for a partial response channel, Singapore, August 4 1999. Coding and signal processing dept., Data Storage Institute. 120 p.

  2. Affanassiev V.B. and Davydov A.A., “Finite Field Towers F(q^p^h): Iterated Presentation and Complexity of Arithmetics for p|(q-1) (submitted).

  3. Ashikhmin A. and Barg A., “Binomial moments of the distance distribution: Bounds and applications,” IEEE Transactions on Information Theory, vol. 45, no. 2, 1999, pp. 435-453.

  4. Ashikhmin A., Barg A., and Litsyn S., “A new upper bound on the reliability function of the Gaussian channel,” IEEE Transactions on Information Theory (submitted, Feb. 1999). [Also DIMACS report 99-06].

  5. Ashikhmin A., Barg A., and Litsyn S., “New upper bounds on generalized Hamming weights of linear codes,” IEEE Transactions on Information Theory, vol. 45, no. 4, 1999, pp. 1258-1263.

  6. Ashikhmin A., Barg A., and Litsyn S., “Polynomial method in coding and information theory,” LANL e-print math-CO/9910175 (http://xxx.lanl.gov; submitted for publication).

  7. Ashikhmin A., Barg A., Knill E., and Litsyn S., “Quantum error detection, I. Statement of the problem,” IEEE Transactions on Information Theory (submitted). [Also LANL e-print quant-ph/9906126].

  8. Ashikhmin A., Barg A., Knill E., and Litsyn S., “Quantum error detection, II. Bounds,” IEEE Transactions on Information Theory (submitted). [Also LANL e-print quant-ph/9906131].

  9. Barg A., “On polynomial invariants of codes, matroids, and the partition function,” DIMACS report 99-54 (http://dimacs.rutgers.edu; submitted for publication).

  10. Barg A. and Ashikhmin A., ”Binomial moments of the distance distribution and the probability of undetected error,” Designs, Codes and Cryptography, vol. 16, no. 2, 1999, pp. 103-116.

  11. Barg A., Krouk E., and van Tilborg H.C.A., “On the complexity of decoding of long linear codes,” IEEE Transactions on Information Theory, vol. 45, no. 5, 1999, pp. 1392-1405.

  12. Barg A. and Zhou S., “Linear-time binary codes correcting localized erasures,” IEEE Transactions on Information Theory, vol. 45, no. 7, 1999.

  13. Barg A. and Zhou S., “A quantum decoding algorithm of the simplex code,” IEEE Transactions on Information Theory (submitted).

  14. Bezrukov S.L., “Edge isoperimetric problems on graphs,” in Proceedings Graph Theory and Combinatorial Biology, Bolyai Society Mathematics Stud. 7, L. Lovasz, A. Gyarfas, G.O.H. Katona, A. Recski, L. Szekely editors, Budapest, 1999, pp. 157-197.

  15. Bezrukov S.L., “On an equivalence in discrete extremal problems,” Discrete Mathematics, vol. 203, 1999, pp. 9-22.

  16. Bezrukov S.L., “Discrete extremal problems,” invited paper for Big Russian Encyclopedia (in print, in Russian).

  17. Bezrukov S.L. and Blokhuis A., “A Kruskal-Katona theorem for the linear lattice,” Europian Journal of Combinatorics, vol. 20, 1999, pp. 123-130.

  18. Bezrukov S.L., Chavez J.D., Harper L.H., Roettger M., and Schroeder U.-P., “The congestion of n-cube layout on a rectangular grid”, Discrete Mathematics (to appear).

  19. Bezrukov S.L., Das S., and Elsaesser R., “An edge isoperimetric problem for powers of the Petersen graph,” Annals of Combinatorics (to appear).

  20. Bezrukov S.L. and Elsaesser R., “The spider poset is Macaulay,” Journal of Combinatorial Theory (to appear).

  21. Bezrukov S.L., Elsaesser R., Monien B., Preis R., and Tillich J.-P., “New spectral lower bounds for the bisection width of graphs” (submitted to STOC-2000).

  22. Bezrukov S.L., Elsaesser R., and Schroeder U.-P., ”On k-partitioning of Hamming graphs,” Discrete Applied Mathematics, vol. 95, 1999, pp. 127-140.

  23. Bezrukov S.L., Elsaesser R., and Schroeder U.-P., “On bounds for the k-partitioning of graphs,” in Proceedings 5th Annual International Conference, COCOON'99, Tokyo, Japan, Lecture Notes in Computer Sciences, vol. 1627, Springer Verlag, 1999.

  24. Bezrukov S.L. and Leck U., “Some new results on Macaulay Posets,” Discrete Mathematics (submitted).

  25. Bezrukov S.L. and Leck U., “The theory of Macaylay posets, Electronic Journal of Combinatorics (submitted). [Also Preprint 99/3, Department of Mathematics, University of Rostock, 1999].

  26. Bezrukov S.L. and Serra O., “A local-global principle for vertex-isoperimetric problems,” Discrete Mathematics (submitted).

  27. Bezrukov S.L., Serra O., and Portas X., “A local-global principle for Macaulay posets,” Order (to appear).

  28. Davydov A.A., "Constructions and families nonbinary linear codes with covering radius 2,” IEEE Transactions on Information Theory, vol. 45, no. 5, 1999, pp. 1679-1686.

  29. Davydov A.A., "New constructions of covering codes," Designs, Codes and Cryptography (to appear).

  30. Davydov A.A. and Ostergard P.R.J., “New linear codes with covering radius 2 and odd basis,” Designs, Codes and Cryptography, vol. 16, no. 1, 1999, pp. 29-39.

  31. Davydov A.A. and Ostergard P.R.J., "New quaternary linear codes with covering radius 2," Finite Fields and Their Applications (to appear).

  32. Davydov A.A. and Ostergard P.R.J., "On saturating sets in small projective geometries,” Europian Journal of Combinatorics (to appear).

  33. Davydov A.A. and Ostergard P.R.J., "Linear codes with covering radius R = 2, 3 and codimension tR,” IEEE Transactions on Information Theory (submitted).

  34. Freudenberger J., Bossert M., Zyablov V., and Shavgulidze S., “Designed permutations for woven codes,” IEEE International Workshop on Concatenated Codes, Schloss Reisensburg by Ulm, Germany, October 1999.

  35. Höst S., Johannesson R., Skopintsev O., and Zyablov V., Asymptotic distance properties of binary woven convolutional codes,” Problems of Information Transmission (submitted, in Russian).

  36. Höst S., Johannesson R., Zigangirov K., and Zyablov V., “Active distances for convolutional Codes,” IEEE Transactions on Information Theory, vol. IT-45, no. 2, 1999, pp. 658-669.

  37. Höst S., Johannesson R., and Zyablov V., “Woven convolutional codes: Encoder properties,” IEEE Transactions on Information Theory (submitted).

  38. Maucher J., Sidorenko V., and Bossert M., “Rectangular bases of linear codes,” accepted to a workshop UK, 1999.

  39. Sidorenko V.R., “Error-correction using code trellises,” Radiotekhnika, no. 12, 1999, pp. 17-23 (in Russian).

  40. Sidorenko V., Martin I., and Honary B., “On the rectangularity of nonlinear block codes,” IEEE Transactions on Information Theory, vol. 45, no. 2, 1999, pp. 720-725.

  41. Sidorenko V., Maucher J., and Bossert M., “Rectangular codes and rectangular algebra,” Lecture Notes in Computer Science, 1719 AAECC, 1999, pp. 252-259.

  42. Sidorenko V., Maucher J., Bossert M., and Lucas R., “Rectangular codes in iterative decoding,” accepted to 3rd ITG Conference on Source and Channel coding, in Muenchen, Jan. 2000.

  43. Trushkin A.V., "On an algorithm for constructing the syndrome trellis," in Proceedings of the 5th International Symposium on Communication Theory and Applications, Ambleside, UK, July 1999.

  44. Wintzell O., Zigangirov D.K., and Zigangirov K. Sh., "On the capacity of a pulse position hopped CDMA system," IEEE International Symposium on Information Theory, Italy, 2000 (to appear).

  45. Zyablov V., Shavgulidze S., and Bossert M., “An introduction to generalized concatenated codes,” European Transactions on Telecommunications (submitted).

  46. Zyablov V., Shavgulidze S., and Johannesson R., “On the error exponent for woven convolutional codes with inner warp,” IEEE Transactions on Information Theory (submitted).

  47. Zyablov V., Shavgulidze S., Skopintsev O., Höst S., and Johannesson R., “On the error exponent for woven convolutional codes with outer warp,” IEEE Transactions on Information Theory, vol. IT-45, no. 5, 1999, pp.1649-1653.

  48. Gitis V. and Vainchtok A. Annual Midterm Progress Report on project Assessment of Seismic Potential in European Large Earthquake Areas “ASPELEA”, EC Project INCO-COPERNICUS, 1999, 15 p.

  49. Gitis V., Osher B., Dovgyallo A., and Gergely T., “An fpproach to online geoinformation modelling,” Proceedings of the 1st International Workshop on Computer Science and Information Technologies. CSIT'99, Moscow, Russia, 1999, pp. 181-186.

  50. Gitis V., Vainchtok A., and Osher B., “G. Papadopoulos seismodynamic pattern of corinthos gulf and thiva-oropos regions.” – Abstracts of the 1st Conference "Advances on natural hazards mitigation," Greece, 3-7 November, 1999.

  51. Gitis V., Vainchtok A., Dovgyallo A., and Osher B., “WWW online system for demonstration, modeling and analysis of geo-referenced data.” – Abstracts of 5th EC-GIS Workshop, Italy, 1999.

  52. Gitis V., Osher B., Dovgyallo A., and Gergely T., “An approach to on-line intelligent geodata analysis,” – Proceedings of the IUGG-99, Birmingham, 19-30 July, 1999, JWS33/E/09-B2 1640-09V.

  53. Gitis V., Osher B., and Papadopoulos G. Analysis of Space-time Parameters of Seismic Process for Corinthos Gulf and Thiva-Oropos Regions in Geotime Instrumental Environment. – Proceedings of the IUGG-99, Birmingham, 19-30 July, 1999, SW1/W/15-B3 1640-10.

  54. Yurkov E. "System for analysis of acoustic process indices under destruction of the rock samples" Journal "Vulkanologiya i Seismologiya," (in print, in Russian).

  55. Yurkov E., “Spatial-energy indices of acoustic emission and seismic processes,” Abstracts of the IUGG-99, Birmingham, 19-30 July, 1999, SW1/E/02-B5, B.225.

  56. Âèòóøêî Ì.À. “Àðõèòåêòóðà èñêóññòâåííûõ èíòåëëåêòóàëüíûõ ñèñòåì”, Pattern Rec. and Image Analysis, vol. 10., 2000 (â ïå÷àòè).

  57. Êëþæåâ Â.Ì., Ñàáëèí Â.Ì., Ìàëüöåâ Ý.Ã., Ïåðåâåðçåâ-Îðëîâ Â.Ñ., Ñòåíèíà È.È. “Ïåðñïåêòèâû ðàçâèòèÿ êîìïüþòåðèçàöèè â ãëàâíîì âîåííîì êëèíè÷åñêîì ãîñïèòàëå”, Ìåäèöèíñêàÿ êèáåðíåòèêà â êëèíè÷åñêîé ïðàêòèêå (ñá. ìàòåðèàëîâ íàó÷í. êîíô. ïîä ðåä. Â. Ì. Êëþæåâà), Ìîñêâà, 1999, ñ. 3-16.

  58. Âàùåíêî Å.À.,. Âèòóøêî Ì.À, Ãóðîâ Í.Ä., Ïåðåâåðçåâ-Îðëîâ Â.Ñ. “Òåõíîëîãèè ñîçäàíèÿ ïàðòíåðñêèõ ñèñòåì”, Ìåäèöèíñêàÿ êèáåðíåòèêà â êëèíè÷åñêîé ïðàêòèêå (ñá. ìàòåðèàëîâ íàó÷í. êîíô. ïîä ðåä. Â. Ì. Êëþæåâà), Ìîñêâà, 1999, ñ. 21-30.

  59. Áåëèêîâà T.Ï., Ñòåíèíà È.È., ßøóíñêàÿ Í.È. “Ïîääåðæêà èíòåðïðåòàöèè èçîáðàæåíèé ñ èñïîëüçîâàíèåì öèôðîâîé îáðàáîòêè è ñèíäðîìíîãî àíàëèçà ïðèçíàêîâ”, Ìåäèöèíñêàÿ êèáåðíåòèêà â êëèíè÷åñêîé ïðàêòèêå (ñá. ìàòåðèàëîâ íàó÷í. êîíô. ïîä ðåä. Â. Ì. Êëþæåâà), Ìîñêâà, 1999, ñ. 115-118.

  60. Belikova T.P., Stenina I.I., Yashunskaya N.I., “An approach to robotics diagnosis of medical images on the base of image processing and syndrome features analysis.” Proc. of the 51st ICB Seminar on Medical Robotics, Biomechanics and Musculoskeletal System, Poland 1999. J. Medical Robotics, 1999, Med. Robotics (in print).

  61. Belikova T.P, Stenina I.I., “Computer-assistance methods to improve image analysis and interpretation in the case of uncertainty,” SPIE Symposium on Medical Imaging, 2000 (accepted).

  62. Sorokin V.N., “New concepts in speech recognition and speech perseption, Peroceedings of the 10th Session of the Russian Acoustical Society, 1999 (in Russian).