49 research outputs found

    Endcoding complexity versus minimum distance

    No full text
    A bound on the minimum distance of a binary error-correcting code is established given constraints on the computational time - space complexity of its encoder where the encoder is modeled as a branching program. The bound obtained asserts that if the encoder uses linear time and sublinear memory in the most general sense, then the minimum distance of the code cannot grow linearly with the block length when the rate is nonvanishing, that is, the minimum relative distance of the code tends to zero in such a setting. The setting is general enough to include nonserially concatenated turbo-like codes and various generalizations. Our argument is based on branching program techniques introduced by Ajtai. The case of constant-depth AND-OR circuit encoders with unbounded fanins are also considered. © 2005 IEEE.Ajtai M., 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, DOI 10.1145-301250.301424; BAZZI L, 2004, IN PRESS IEEE T INF; Bazzi L. M. J., 2003, THESIS MIT CAMBRIDGE; Berrou C., 1993, P IEEE INT C COMM GE, P1064; BORODIN A, 1982, SIAM J COMPUT, V11, P287, DOI 10.1137-0211022; Divsalar D., 1998, Proceedings. Thiry-Sixth Annual Allerton Conference on Communication, Control, and Computing; Hastad J., 1986, THESIS MIT CAMBRIDGE; Jin H, 2002, IEEE T INFORM THEORY, V48, P1451; Kahale N., 1998, Proceedings. 1998 IEEE International Symposium on Information Theory (Cat. No.98CH36252), DOI 10.1109-ISIT.1998.708611; KAHALE N, IN PRESS IEEE T INF; Spielman DA, 1996, IEEE T INFORM THEORY, V42, P1723, DOI 10.1109-18.55666817151

    Polylogarithmic independence can fool DNF formulas

    No full text
    We show that any k-wise independent probability distribution on [0, 1] n O (m 2.2. 2- √k-10)-fools any boolean function computable by an m-clause disjunctive normal form (DNF) (or conjunctive normal form (CNF)) formula on n variables. Thus, for each constant e andgt; 0, there is a constant c andgt; 0 such that any boolean function computable by an m-clause DNF (or CNF) formula is m -e-fooled by any c log 2m-wise probability distribution. This resolves up to an O (logm) factor the depth-2 circuit case of a conjecture due to Linial and Nisan [Combinatorica, 10 (1990), pp. 349-365]. The result is equivalent to a new characterization of DNF (or CNF) formulas by low degree polynomials. It implies a similar statement for probability distributions with the small bias property. Using known explicit constructions of small probability spaces having the limited independence property or the small bias property, we directly obtain a large class of explicit pseudorandom generators of O (log 2 m log n)-seed length for m-clause DNF (or CNF) formulas on n variables, improving previously known seed lengths. © 2009 Society for Industrial and Applied Mathematics.Ajtai M., 1985, P 26 IEEE S FDN COMP, P11; Alon N, 2003, INFORM PROCESS LETT, V88, P107, DOI 10.1016-S0020-0190(03)00359-4; ALON N, 1992, RANDOM STRUCT ALGOR, V3, P289, DOI 10.1002-rsa.3240030308; ASPNES J, 1994, COMBINATORICA, V14, P135, DOI 10.1007-BF01215346; BAZZI L, 2007, P 48 ANN IEEE S FDN, P63; Bazzi L. M. J., 2003, THESIS MIT CAMBRIDGE; BEIGEL R, 1991, STRUCT COMPL TH CONF, P286, DOI 10.1109-SCT.1991.160270; BLUM M, 1984, SIAM J COMPUT, V13, P850, DOI 10.1137-0213053; Hastad J., 1986, THESIS MIT CAMBRIDGE; Impagliazzo R., 1997, P 29 ANN ACM S THEOR, P220, DOI 10.1145-258533.258590; Kahn J., 1988, P 29 ANN S FDN COMP, P68, DOI 10.1109-SFCS.1988.21923; LECHNER RJ, 1971, RECENT DEV SWITCHING, P121; LINIAL N, 1990, COMBINATORICA, V10, P349, DOI 10.1007-BF02128670; LINIAL N, 1993, J ACM, V40, P607, DOI 10.1145-174130.174138; Luby M, 1996, ALGORITHMICA, V16, P415, DOI 10.1007-BF01940873; Luby M., 1985, P 17 ANN ACM S THEOR, P1, DOI 10.1145-22145.22146; Luby M., 1993, Proceedings of the 2nd Israel Symposium on Theory and Computing Systems (Cat. No.93TH0520-7), DOI 10.1109-ISTCS.1993.253488; NAOR J, 1993, SIAM J COMPUT, V22, P838, DOI 10.1137-0222053; Nisan N., 1994, Computational Complexity, V4, DOI 10.1007-BF01263419; NISAN N, 1988, P 29 IEEE S FDN COMP, P2, DOI 10.1109-SFCS.1988.21916; Razborov A. A., 1987, MAT ZAMETKI, V41, p[598, 623]; RAZBOROV AA, 2008, EL C COMP COMPL; STANELY RP, 1997, ENUMERATIVE COMBINAT, V1; TREVISAN L, 2004, P APPROX RANDOM, P417; Vazirani U. V., 1986, THESIS U CALIFORNIA; Yao A., 1982, P 23 IEEE S FDN COMP, P8016111

    Some randomized code constructions from group actions

    No full text
    We study in this paper randomized constructions of binary linear codes that are invariant under the action of some group on the bits of the codewords. We study a non-Abelian randomized construction corresponding to the action of the dihedral group on a single copy of itself as well as a randomized Abelian construction based on the action of an Abelian group on a number of disjoint copies of itself. Cyclic codes have been extensively studied over the last 40 years. However, it is still an open question as to whether there exist asymptotically good binary cyclic codes. We argue that by using a slightly more complex group than a cyclic group, namely, the dihedral group, the existence of asymptotically good codes that are invariant under the action of the group on itself can be guaranteed. In particular, we show that, for infinitely many block lengths, a random ideal in the binary group algebra of the dihedral group is an asymptotically good rate-half code with a high probability. We argue also that a random code that is invariant under the action of an Abelian group G of odd order on k disjoint copies of itself satisfies the binary Gilbert-Varshamov (GV) bound with a high probability for rate 1-k under a condition on the family of groups. The underlying condition is in terms of the growth of the smallest dimension of a nontrivial F2-representation of the group and is satisfied by roughly most Abelian groups of odd order, and specifically by almost all cyclic groups of prime order. © 2006 IEEE.Burrow M., 1965, REPRESENTATION THEOR; CHEN CL, 1969, INFORM CONTROL, V15, P407, DOI 10.1016-S0019-9958(69)90497-5; CHEPYZHOV V, 1993, PROBL PEREDACHI INF, V28, P33; Curtis C.W., 1962, REPRESENTATION THEOR; KASAMI T, 1974, IEEE T INFORM THEORY, V20, P679, DOI 10.1109-TIT.1974.1055262; LIDL R, 1983, FINITE FIELDS NUMBER; LINT X, 1999, GRADUATE TEXTS MATH; LUBOTZKY A, 1988, COMBINATORICA, V8, P261, DOI 10.1007-BF02126799; MACWILLIAMS FJ, 1969, COMBINATORIAL MATH I, P317; MACWILLIAMS JF, 1992, THEORY ERROR CORRECT; Margulis G. A., 1988, Problems of Information Transmission, V24; MCDONALD, 1974, FINITE RINGS IDENTIT; PIRET P, 1985, IEEE T INFORM THEORY, V31, P520, DOI 10.1109-TIT.1985.1057061; Pless V.S., 1998, HDB CODING THEORY; Shparlinsky I. E., 1986, PROBLEMY PEREDACHI I, V22, P43; Sipser M, 1996, IEEE T INFORM THEORY, V42, P1710, DOI 10.1109-18.556667; WARD HN, 1974, J ALGEBRA, V29, P150, DOI 10.1016-0021-8693(74)90120-365

    Zetting door wegophoging - casestudie A2 Holendrecht Maarssen

    No full text
    De toepasbaarheid van recente zettingsmodellen in MSettle 8.2 is geëvalueerd, door toetsing aan metingen op de A2 verbreding nabij Vinkeveen. De dikke veenlaag is daar versneld samengedrukt door gebruik van verticale drains en tijdelijke voorbelasting. Naast weggenomen overhoogte is op een deel ook voorbelast door tijdelijke onderdruk (BeauDrain). Voor de voorspelling zijn isotache zettingsmodellen gebruikt, in combinatie met het nieuwe Darcy consolidatiemodel. Deze combinatie is als enige geschikt voor een voorspelling van restzetting na weggenomen voorbelasting. Bandbreedtes in het ontwerp volgen uit invoer van de horizontale spreiding in de verticaal gemiddelde materiaaleigenschappen. Een automatische zakbaakfit past de materiaalparameters tijdens de uitvoering aan. De metingen zijn tevens van invloed op de voorspelde bandbreedte, afhankelijk van de kwaliteit van de fit. In totaal zijn 14 doorsneden bekeken, met drie zakbaken per doorsnede. De gemeten zettingen op de as blijken veelal te liggen binnen de voorspelde band uit de ontwerpberekening. Op de flanken zijn de afwijkingen groter, vermoedelijk vanwege de invloed van horizontale vervormingen. De gevonden fitfactoren langs de as hebben realistische verwachtingswaarden en horizontale spreidingen. Bandbreedtebepaling blijkt goed bruikbaar om risico’s te beheersen. Combinatie met een zakbaakfit kan risico’s tijdens uitvoering verder verkleinen, maar vereist wel veel goede metingen en een kritische analyse van fitfactoren. Een fit door parameteraanpassing is alleen toepasbaar indien de afwijking tussen voorspelling en meting niet wordt veroorzaakt door modelbeperkingen of door fouten in belasting en laagindeling. De kwaliteit van een restzettingsvoorspelling blijft onzeker, zolang de werkelijke relatie tussen hogere leeftijd, kruipsnelheid en overconsolidatie zo slecht bekend is. Lange duur metingen zijn daarom dringend nodig voor validatie en mogelijke modelverbetering

    Biologische sedimentatie van gesuspendeerd slib en sedimentstabilisatie

    No full text
    In het kader van het Delft cluster onderzoeksprogramma Wetlands onderzoekt ‘Biotools’ methoden om de concentratie gesuspendeerd materiaal in een zoetwateromgeving versneld te laten bezinken door toevoeging van biologische additieven (biosedimentatie) en polysacchariden die flocculatie teweeg brengen waardoor gesuspendeerd slib sneller bezinkt (bioflocculatie). In de proefopzet werden 4 varianten vergeleken met de blanco (slib zonder verdere toevoeging): toevoeging van waterzuiveringsslib, toevoeging van een hogere concentratie waterzuiveringsslib, toevoeging van kationische en toevoeging van anionische polysacchariden. De eerste twee varianten zorgen initieel voor een snellere (bio)sedimentatie. De varianten met geladen polymeren zorgen voor uiteenlopende effecten: algengroei trad (sneller) op en kationen zorgen voor een dispersie van kleilamellen waardoor het materiaal langer in suspensie blijft en trager bezinkt. Behalve de initiële bezinksnelheid en concentratie bij evenwicht werd ook gekeken naar de effecten in de tijd. De proevenreeks duurde 11 dagen, en in de loop van de tijd ging de bezinksnelheid in alle proeven omlaag (minst in de blanco, maar de absolute bezinksnelheid was niet de minste van alle proeven in het begin)

    An Algorithm to Minimize the Zero-Flow Error in Transit-Time Ultrasonic Flow Meters

    No full text
    Transit-time ultrasonic flow meters are widely used in industry to measure fluid flow. In practice ultrasonic flow meters either show a zero-flow error or suffer from a significant random error due to a limited signal-to-noise ratio, requiring a significant amount of averaging to achieve good precision. This work presents a method that minimizes the zero-flow error whilst keeping the random error low, independent of the hardware used. The proposed algorithm can adjust to changing zero-flow errors while a flow is present. The technique combines the benefits of two common methods of determining the transit-time difference between the upstream and downstream ultrasonic waves: cross-correlation and zero-crossing detection. The algorithm is verified experimentally using a flow-loop. It is shown that the zero-flow error can be greatly reduced without compromising the random error or increasing circuit complexity.Electronic InstrumentationImPhys/Medical Imagin

    Microspheres with Ultrahigh Holmium Content for Radioablation of Malignancies

    No full text
    Purpose The aim of this study was to develop microspheres with an ultra high holmium content which can be neutron activated for radioablation of malignancies. These microspheres are proposed to be delivered selectively through either intratumoral injections into solid tumors or administered via an intravascularly placed catheter. Methods Microspheres were prepared by solvent evaporation, using holmium acetylacetonate (HoAcAc) crystals as the sole ingredient. Microspheres were characterized using light and scanning electron microscopy, coulter counter, titrimetry, infrared and Raman spectroscopy, differential scanning calorimetry, X-ray powder diffraction, magnetic resonance imaging (MRI), and X-ray computed tomography (CT). Results Microspheres, thus prepared displayed a smooth surface. The holmium content of the HoAcAc microspheres (44% (w/w)) was higher than the holmium content of the starting material, HoAcAc crystals (33% (w/w)). This was attributed to the loss of acetylacetonate from the HoAcAc complex, during rearrangement of acetylacetonate around the holmium ion. The increase of the holmium content allows for the detection of (sub)microgram amounts of microspheres using MRI and CT. Conclusions HoAcAc microspheres with an ultra-high holmium content were prepared. These microspheres are suitable for radioablation of tumors by intratumoral injections or treatment of liver tumors through transcatheter administration.Radiation, Radionuclides and ReactorsApplied Science
    corecore